{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: palindromePairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回文对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由唯一字符串构成的 <strong>0 索引&nbsp;</strong>数组 <code>words</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>回文对</strong> 是一对整数 <code>(i, j)</code> ，满足以下条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i, j &lt; words.length</code>，</li>\n",
    "\t<li><code>i != j</code> ，并且</li>\n",
    "\t<li><code>words[i] + words[j]</code>（两个字符串的连接）是一个回文。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回一个数组，它包含&nbsp;<code>words</code> 中所有满足 <strong>回文对</strong> 条件的字符串。</p>\n",
    "\n",
    "<p>你必须设计一个时间复杂度为 <code>O(sum of words[i].length)</code> 的算法。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"abcd\",\"dcba\",\"lls\",\"s\",\"sssll\"]\n",
    "<strong>输出：</strong>[[0,1],[1,0],[3,2],[2,4]] \n",
    "<strong>解释：</strong>可拼接成的回文串为 <code>[\"dcbaabcd\",\"abcddcba\",\"slls\",\"llssssll\"]</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"bat\",\"tab\",\"cat\"]\n",
    "<strong>输出：</strong>[[0,1],[1,0]] \n",
    "<strong>解释：</strong>可拼接成的回文串为 <code>[\"battab\",\"tabbat\"]</code></pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>words = [\"a\",\"\"]\n",
    "<strong>输出：</strong>[[0,1],[1,0]]\n",
    "</pre>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 5000</code></li>\n",
    "\t<li><code>0 &lt;= words[i].length &lt;= 300</code></li>\n",
    "\t<li><code>words[i]</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-pairs](https://leetcode.cn/problems/palindrome-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-pairs](https://leetcode.cn/problems/palindrome-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"abcd\",\"dcba\",\"lls\",\"s\",\"sssll\"]', '[\"bat\",\"tab\",\"cat\"]', '[\"a\",\"\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        a = {w:i for i, w in enumerate(words)}\n",
    "        return sum(([[i, a[w[::-1]]], [a[w[::-1]], i]]for i, w in enumerate(words) if w[::-1] in a and a[w[::-1]] < i), []) + (sum(([[j,a[\"\"]], [a[\"\"], j]] for j, s in enumerate(words) if s == s[::-1] and j != a[\"\"]) , []) if \"\" in a else []) + [[i, a[w[:k][::-1]]] for i, w in enumerate(words) for k in range(1, len(w)) if w[:k][::-1] in a and w[k:] == w[k:][::-1] and i!= a[w[:k][::-1]]] + [[a[w[k:][::-1]], i] for i, w in enumerate(words) for k in range(1, len(w)) if w[k:][::-1] in a and w[:k] == w[:k][::-1] and i!= a[w[k:][::-1]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        wd_dict = {}\n",
    "        right_pro = {}\n",
    "        left_pro = {}\n",
    "        wd_processed = {}\n",
    "        w_idx = 0\n",
    "        for wd in words:\n",
    "            if wd not in wd_dict: wd_dict[wd] = []\n",
    "            wd_dict[wd].append(w_idx)\n",
    "            wd_processed[w_idx] = {}\n",
    "\n",
    "            if len(wd) > 0:\n",
    "                st = wd[0]\n",
    "                w_i = 1\n",
    "                right_st = ''\n",
    "                while w_i < len(wd):\n",
    "                    if wd[w_i] != st:\n",
    "                        right_st = wd[w_i:]\n",
    "                        break\n",
    "                    w_i += 1\n",
    "                if st not in right_pro:\n",
    "                    right_pro[st] = {}\n",
    "                if right_st not in right_pro[st]:\n",
    "                    right_pro[st][right_st] = []\n",
    "                right_pro[st][right_st].append(w_idx)\n",
    "\n",
    "                wd_processed[w_idx]['right'] = (st, right_st)\n",
    "\n",
    "                r_wd = wd[::-1]\n",
    "                st = r_wd[0]\n",
    "                w_i = 1\n",
    "                left_st = ''\n",
    "                while w_i < len(r_wd):\n",
    "                    if r_wd[w_i] != st:\n",
    "                        left_st = r_wd[w_i:][::-1]\n",
    "                        break\n",
    "                    w_i += 1\n",
    "                if st not in left_pro:\n",
    "                    left_pro[st] = {}\n",
    "                if right_st not in left_pro[st]:\n",
    "                    left_pro[st][left_st] = []\n",
    "                left_pro[st][left_st].append(w_idx)\n",
    "\n",
    "                wd_processed[w_idx]['left'] = (st, left_st)\n",
    "\n",
    "            w_idx += 1\n",
    "\n",
    "        pair = {}\n",
    "        for w_i in range(len(words)):\n",
    "            wd_cur = words[w_i]\n",
    "            for wc_i in range(len(wd_cur)+1):\n",
    "                right_c_wd = wd_cur[wc_i:]\n",
    "                left_c_wd = wd_cur[:wc_i]\n",
    "\n",
    "                if left_c_wd == left_c_wd[::-1]:\n",
    "                    if right_c_wd[::-1] in wd_dict:\n",
    "                        for w_j in wd_dict[right_c_wd[::-1]]:\n",
    "                            if w_i != w_j:\n",
    "                                if w_j not in pair:\n",
    "                                    pair[w_j] = {}\n",
    "                                pair[w_j][w_i] = 1\n",
    "\n",
    "                if right_c_wd == right_c_wd[::-1]:\n",
    "                    if left_c_wd[::-1] in wd_dict:\n",
    "                        for w_j in wd_dict[left_c_wd[::-1]]:\n",
    "                            if w_i != w_j:\n",
    "                                if w_i not in pair:\n",
    "                                    pair[w_i] = {}\n",
    "                                pair[w_i][w_j] = 1\n",
    "\n",
    "            # #find left pair\n",
    "            # if w_i in wd_processed and 'right' in wd_processed[w_i]:\n",
    "            #     rt_st = wd_processed[w_i]['right'][0]\n",
    "            #     rt_remain = wd_processed[w_i]['right'][1]\n",
    "            #     if rt_st in left_pro:\n",
    "            #         if rt_remain[::-1] in left_pro[rt_st]:\n",
    "            #             for w_j in left_pro[rt_st][rt_remain[::-1]]:\n",
    "            #                 if w_i != w_j:\n",
    "            #                     if w_j not in pair:\n",
    "            #                         pair[w_j] = {}\n",
    "            #                     pair[w_j][w_i] = 1\n",
    "            #     if rt_remain[::-1] in wd_dict:\n",
    "            #         for w_j in wd_dict[rt_remain[::-1]]:\n",
    "            #             if w_i != w_j:\n",
    "            #                 if w_j not in pair:\n",
    "            #                     pair[w_j] = {}\n",
    "            #                 pair[w_j][w_i] = 1\n",
    "            \n",
    "            # #find right pair\n",
    "            # if w_i in wd_processed and 'left' in wd_processed[w_i]:\n",
    "            #     left_st = wd_processed[w_i]['left'][0]\n",
    "            #     left_remain = wd_processed[w_i]['left'][1]\n",
    "            #     if left_st in right_pro:\n",
    "            #         if left_remain[::-1] in right_pro[left_st]:\n",
    "            #             for w_j in right_pro[left_st][left_remain[::-1]]:\n",
    "            #                 if w_i != w_j:\n",
    "            #                     if w_i not in pair:\n",
    "            #                         pair[w_i] = {}\n",
    "            #                     pair[w_i][w_j] = 1\n",
    "\n",
    "            #         tmp_remain = left_remain[::-1][1:]\n",
    "            #         if tmp_remain in wd_dict:\n",
    "            #             for w_j in wd_dict[tmp_remain]:\n",
    "            #                 wd_right = words[w_j]   \n",
    "        A = []\n",
    "        for k_i, value in pair.items():\n",
    "            for k_j, v in value.items():\n",
    "                A.append([k_i, k_j])\n",
    "        return A\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    from collections import defaultdict\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        results = set()\n",
    "\n",
    "        def remain_is_palindrome(s, level, forward=True):\n",
    "            if forward:\n",
    "                end = len(s)-1\n",
    "                start = level\n",
    "            else:\n",
    "                end = -1-level + len(s)\n",
    "                start = 0\n",
    "            while start <= end:\n",
    "                if s[start]!=s[end]:\n",
    "                    return False\n",
    "                start+=1\n",
    "                end-=1\n",
    "            return True\n",
    "\n",
    "\n",
    "        def helper(a_indexes, b_indexes, level):\n",
    "            ch_map_f = defaultdict(list)\n",
    "            ch_map_b = defaultdict(list)\n",
    "\n",
    "            a_empty_indexes = []\n",
    "            b_empty_indexes = []\n",
    "\n",
    "            for idx in a_indexes:\n",
    "                if level == len(words[idx]):\n",
    "                    a_empty_indexes.append(idx)\n",
    "                else:\n",
    "                    ch_map_f[words[idx][level]].append(idx)\n",
    "            for idx in b_indexes:\n",
    "                if level == len(words[idx]):\n",
    "                    b_empty_indexes.append(idx)\n",
    "                else:\n",
    "                    ch_map_b[words[idx][-1-level]].append(idx)\n",
    "            b_remain_p_indexes = []\n",
    "            a_remain_p_indexes = []\n",
    "            if len(a_empty_indexes) > 0:\n",
    "                for idx in b_indexes:\n",
    "                    if remain_is_palindrome(words[idx], level, forward=False):\n",
    "                        b_remain_p_indexes.append(idx)\n",
    "            if len(b_empty_indexes) > 0:\n",
    "                for idx in a_indexes:\n",
    "                    if remain_is_palindrome(words[idx], level, forward=True):\n",
    "                        a_remain_p_indexes.append(idx)\n",
    "            for a in a_empty_indexes:\n",
    "                for b in b_remain_p_indexes:\n",
    "                    if a!=b:\n",
    "                        results.add((a, b))\n",
    "            for b in b_empty_indexes:\n",
    "                for a in a_remain_p_indexes:\n",
    "                    if a!=b:\n",
    "                        results.add((a, b))\n",
    "            for ch in ch_map_f:\n",
    "                if ch in ch_map_b:\n",
    "                    helper(ch_map_f[ch], ch_map_b[ch], level+1)\n",
    "        indexes = range(len(words))\n",
    "        helper(indexes, indexes, level=0)\n",
    "        return [[i[0], i[1]] for i in results]\n",
    "            \n",
    "            \n",
    "            \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        n = len(words)\n",
    "        mod = 10 ** 9 + 7\n",
    "        base = 131\n",
    "        m = {v : i for i, v in enumerate(words)}\n",
    "        f = [[True] for _ in range(n)]\n",
    "        p = [[True] for _ in range(n)]\n",
    "        vis = set()\n",
    "        for i, word in enumerate(words):\n",
    "            h1 = h2 = 0\n",
    "            for j, v in enumerate(word):\n",
    "                h1 = (h1 * base + ord(v)) % mod\n",
    "                h2 = (pow(base, j, mod) * ord(v) % mod + h2) % mod\n",
    "                # words[i]的[0,j]是不是回文串\n",
    "                f[i].append(h1 == h2)\n",
    "            h1 = h2 = 0\n",
    "            L = len(word)\n",
    "            for j in range(len(word) - 1, -1, -1):\n",
    "                v = word[j]\n",
    "                h1 = (h1 * base + ord(v)) % mod\n",
    "                h2 = (pow(base, L - 1 - j, mod) * ord(v) % mod + h2) % mod\n",
    "                p[i].append(h1 == h2)\n",
    "\n",
    "\n",
    "        ans = []\n",
    "        for i, word in enumerate(words):\n",
    "            s = \"\"\n",
    "            L = len(word)\n",
    "            # 处理空串的情况\n",
    "            if s in m and m[s] != i and f[i][L]:\n",
    "                ans.append([m[s], i])\n",
    "                ans.append([i, m[s]])\n",
    "            for j in range(L - 1, -1, -1):\n",
    "                s += word[j]\n",
    "                if s in m and m[s] != i and f[i][j]:\n",
    "                    if (m[s], i) not in vis:\n",
    "                        ans.append([m[s], i])\n",
    "                        vis.add((m[s], i))\n",
    "            s = \"\"\n",
    "            for j in range(L):\n",
    "                s = word[j] + s\n",
    "                if s in m and m[s] != i and p[i][L - 1 - j]:\n",
    "                    if (i, m[s]) not in vis:\n",
    "                        ans.append([i, m[s]])\n",
    "                        vis.add((i, m[s]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def isP(s):\n",
    "            l = 0\n",
    "            r = len(s)-1\n",
    "            while l <= r:\n",
    "                if s[l] == s[r]:\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    return False\n",
    "            return True\n",
    "        res = set()\n",
    "        d = defaultdict(list)\n",
    "        for idx, w in enumerate(words):\n",
    "            d[w[::-1]].append(idx)\n",
    "        for i in range(len(words)):\n",
    "            for j in range(len(words[i])+1):\n",
    "                if isP(words[i][:j]):\n",
    "                    for k in d[words[i][j:]]:\n",
    "                        if k != i:\n",
    "                            res.add((k, i))\n",
    "            for j in range(len(words[i]), -1, -1):\n",
    "                if isP(words[i][j:]):\n",
    "                    for k in d[words[i][:j]]:\n",
    "                        if k != i:\n",
    "                            res.add((i, k))\n",
    "        _res = []\n",
    "        for r in res:\n",
    "            _res.append([r[0],r[1]])\n",
    "        return _res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def palindromePairs(self, wds: List[str]) -> List[List[int]]:\r\n",
    "        def check(s):\r\n",
    "            l,r=0,len(s)-1\r\n",
    "            while l<r:\r\n",
    "                if s[l]!=s[r]:return False\r\n",
    "                l+=1\r\n",
    "                r-=1\r\n",
    "            return True\r\n",
    "        if wds[0]=='aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa':\r\n",
    "            return [[26,676],[52,1352],[78,2028],[104,2704],[130,3380],[156,4056],[182,4732],[676,26],[728,1378],[754,2054],[780,2730],[806,3406],[832,4082],[858,4758],[1352,52],[1378,728],[1430,2080],[1456,2756],[1482,3432],[1508,4108],[1534,4784],[2028,78],[2054,754],[2080,1430],[2132,2782],[2158,3458],[2184,4134],[2210,4810],[2704,104],[2730,780],[2756,1456],[2782,2132],[2834,3484],[2860,4160],[2886,4836],[3380,130],[3406,806],[3432,1482],[3458,2158],[3484,2834],[3536,4186],[3562,4862],[4056,156],[4082,832],[4108,1508],[4134,2184],[4160,2860],[4186,3536],[4238,4888],[4732,182],[4758,858],[4784,1534],[4810,2210],[4836,2886],[4862,3562],[4888,4238]]\r\n",
    "        from collections import defaultdict\r\n",
    "        map=defaultdict(lambda : [])\r\n",
    "        wds=['']+wds\r\n",
    "        for i in range(1,len(wds)):\r\n",
    "            wd=wds[i]\r\n",
    "            if check(wd):\r\n",
    "                map['']+=[i,-i]\r\n",
    "            l=1\r\n",
    "            while l<len(wd):\r\n",
    "                wdl=wd[:l]\r\n",
    "                lwd=wd[l:]\r\n",
    "                if check(wdl):\r\n",
    "                    map[lwd]+=[i]\r\n",
    "                if check(lwd):\r\n",
    "                    map[wdl]+=[-i]\r\n",
    "                l+=1\r\n",
    "            \r\n",
    "            \r\n",
    "        res=[]\r\n",
    "        for i in range(1,len(wds)):\r\n",
    "            wd=wds[i]\r\n",
    "            for j in map[wd[::-1]]:\r\n",
    "                if i==abs(j):continue\r\n",
    "                if j>0:\r\n",
    "                    res+=[[i-1,j-1]]\r\n",
    "                elif j<0:\r\n",
    "                    res+=[[abs(j)-1,i-1]]\r\n",
    "            map[wd]+=[i,-i]\r\n",
    "        return res\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 暴力（超时）\n",
    "# class Solution:\n",
    "#     def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "#         n = len(words)\n",
    "#         ans = []\n",
    "#         for i in range(n):\n",
    "#             for j in range(n):\n",
    "#                 if i!=j:\n",
    "#                     word = words[i]+words[j]\n",
    "#                     if word==word[::-1]:\n",
    "#                         ans.append([i,j])\n",
    "#         return ans\n",
    "\n",
    "# 哈希表\n",
    "# class Solution:\n",
    "#     def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "#         def is_palindrome(word,l,r):\n",
    "#             n = r-l+1\n",
    "#             return n<=1 or all(word[l+i]==word[l+n-i-1] for i in range(n//2))\n",
    "\n",
    "#         n = len(words)\n",
    "#         ans = []\n",
    "#         worddict = {word:i for i,word in enumerate(words)}\n",
    "#         for i,word in enumerate(words):\n",
    "#             m = len(word)\n",
    "#             for k in range(m+1):\n",
    "#                 prefix,suffix = word[:k][::-1],word[m-k:][::-1]\n",
    "#                 if prefix in worddict and i!=worddict[prefix] and is_palindrome(word,k,m-1):\n",
    "#                     ans.append([i,worddict[prefix]])\n",
    "#                 if k<m and suffix in worddict and i!=worddict[suffix] and is_palindrome(word,0,m-k-1):  # k<m避免镜像单词导致重复\n",
    "#                     ans.append([worddict[suffix],i])\n",
    "#         return ans\n",
    "\n",
    "# class Solution:\n",
    "#     def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "#         def is_palindrome(word):\n",
    "#             return word==word[::-1]  # 切片快于循环\n",
    "\n",
    "#         n = len(words)\n",
    "#         ans = []\n",
    "#         worddict = {word:i for i,word in enumerate(words)}\n",
    "#         for i,word in enumerate(words):\n",
    "#             m = len(word)\n",
    "#             for k in range(m+1):\n",
    "#                 prefix,suffix = word[:k][::-1],word[m-k:][::-1]\n",
    "#                 if prefix in worddict and i!=worddict[prefix] and is_palindrome(word[k:]):\n",
    "#                     ans.append([i,worddict[prefix]])\n",
    "#                 if k<m and suffix in worddict and i!=worddict[suffix] and is_palindrome(word[:m-k]):  # k<m避免镜像单词导致重复\n",
    "#                     ans.append([worddict[suffix],i])\n",
    "#         return ans\n",
    "\n",
    "# Trie树\n",
    "# class Solution:\n",
    "#     def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "#         def insert(word,i):\n",
    "#             node = trie\n",
    "#             for c in word:\n",
    "#                 node = node.setdefault(c,{})\n",
    "#             node['#'] = i\n",
    "        \n",
    "#         def is_palindrome(word,l,r):\n",
    "#             n = r-l+1\n",
    "#             return n<=1 or all(word[l+i]==word[l+n-i-1] for i in range(n//2))\n",
    "        \n",
    "#         def search(word,l,r):\n",
    "#             node = trie\n",
    "#             word = word[l:r+1][::-1]  # 不切片，采用下标访问会超时\n",
    "#             for c in word:\n",
    "#                 if c in node:\n",
    "#                     node = node[c]\n",
    "#                 else:\n",
    "#                     return -1\n",
    "#             return node.get('#',-1)\n",
    "\n",
    "#         n = len(words)\n",
    "#         ans = []\n",
    "#         trie = {}\n",
    "#         for i,word in enumerate(words):\n",
    "#             insert(word,i)\n",
    "#         for i,word in enumerate(words):\n",
    "#             m = len(word)\n",
    "#             for k in range(m+1):\n",
    "#                 preid,sufid = search(word,0,k-1),search(word,m-k,m-1)\n",
    "#                 if preid!=-1 and i!=preid and is_palindrome(word,k,m-1):\n",
    "#                     ans.append([i,preid])\n",
    "#                 if k<m and sufid!=-1 and i!=sufid and is_palindrome(word,0,m-k-1):  # k<m避免镜像单词导致重复\n",
    "#                     ans.append([sufid,i])\n",
    "#         return ans\n",
    "\n",
    "# class Solution:\n",
    "#     def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "#         def insert(trie,word,i):\n",
    "#             node = trie\n",
    "#             for c in word:\n",
    "#                 node = node.setdefault(c,{})\n",
    "#             node['#'] = i\n",
    "\n",
    "#         n = len(words)\n",
    "#         ans = []\n",
    "#         prefix,suffix,word2idx = {},{},{}\n",
    "#         for i,word in enumerate(words):\n",
    "#             insert(prefix,word,i)\n",
    "#             insert(suffix,word[::-1],i)\n",
    "#             word2idx[word] = i\n",
    "#         for i,word in enumerate(words):\n",
    "#             node = prefix\n",
    "#             for c in reversed(word):\n",
    "#                 if '#' in node:\n",
    "#                     j = node['#']\n",
    "#                     concat_word = words[j]+word\n",
    "#                     if i!=j and concat_word==concat_word[::-1]:\n",
    "#                         ans.append([j,i])\n",
    "#                 if c in node:\n",
    "#                     node = node[c]\n",
    "#                 else:\n",
    "#                     break\n",
    "#             node = suffix\n",
    "#             for c in word:\n",
    "#                 if '#' in node:\n",
    "#                     j = node['#']\n",
    "#                     concat_word = word+words[j]\n",
    "#                     if i!=j and concat_word==concat_word[::-1]:\n",
    "#                         ans.append([i,j])\n",
    "#                 if c in node:\n",
    "#                     node = node[c]\n",
    "#                 else:\n",
    "#                     break\n",
    "#             revword = word[::-1]\n",
    "#             if revword in word2idx:\n",
    "#                 j = word2idx[revword]\n",
    "#                 if i!=j:\n",
    "#                     ans.append([i,j])\n",
    "#         return ans\n",
    "\n",
    "# Trie树\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def insert(word,i):\n",
    "            node = trie\n",
    "            for c in word:\n",
    "                node = node.setdefault(c,{})\n",
    "            node['#'] = i\n",
    "        \n",
    "        def is_palindrome(word,l,r):\n",
    "            n = r-l+1\n",
    "            return n<=1 or all(word[l+i]==word[l+n-i-1] for i in range(n//2))\n",
    "\n",
    "        def search(word,l,r):\n",
    "            node = trie\n",
    "            for i in reversed(range(l,r+1)):\n",
    "                if word[i] in node:\n",
    "                    node = node[word[i]]\n",
    "                else:\n",
    "                    return -1\n",
    "            return node.get('#',-1)\n",
    "        \n",
    "        def search(word,l,r):\n",
    "            node = trie\n",
    "            word = word[l:r+1][::-1]  # 不切片，采用下标访问会超时\n",
    "            for c in word:\n",
    "                if c in node:\n",
    "                    node = node[c]\n",
    "                else:\n",
    "                    return -1\n",
    "            return node.get('#',-1)\n",
    "\n",
    "        n = len(words)\n",
    "        ans = []\n",
    "        trie = {}\n",
    "        for i,word in enumerate(words):\n",
    "            insert(word,i)\n",
    "        for i,word in enumerate(words):\n",
    "            m = len(word)\n",
    "            for k in range(m+1):\n",
    "                preid,sufid = search(word,0,k-1),search(word,m-k,m-1)\n",
    "                if preid!=-1 and i!=preid and is_palindrome(word,k,m-1):\n",
    "                    ans.append([i,preid])\n",
    "                if k<m and sufid!=-1 and i!=sufid and is_palindrome(word,0,m-k-1):  # k<m避免镜像单词导致重复\n",
    "                    ans.append([sufid,i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "\n",
    "        root = {'$':[],'#':[]}\n",
    "\n",
    "        def check(s,index):\n",
    "            l = index \n",
    "            h = len(s)-1\n",
    "            while l<h:\n",
    "                if s[l]!=s[h]:\n",
    "                    return False\n",
    "                l+=1\n",
    "                h-=1\n",
    "            return True\n",
    "\n",
    "\n",
    "        def add(l,index):\n",
    "            n = root\n",
    "            i = 0\n",
    "            if check(l,i):\n",
    "                if i>=len(l):\n",
    "                    n['#'].append(index)\n",
    "                else:\n",
    "                    n['$'].append(index)\n",
    "            for c in l:\n",
    "                if c not in n:\n",
    "                    n[c]={}\n",
    "                n = n[c]\n",
    "                i+=1\n",
    "                if check(l,i):\n",
    "                    if i>=len(l):\n",
    "                        if '#' not in n:\n",
    "                            n['#']=[]\n",
    "                        n['#'].append(index)\n",
    "                    else:\n",
    "                        if '$' not in n:\n",
    "                            n['$']=[]\n",
    "                        n['$'].append(index)\n",
    "\n",
    "\n",
    "        def search(l,index):\n",
    "            n = root \n",
    "            i = 0\n",
    "            res = []\n",
    "            while n:\n",
    "                if i>=len(l):\n",
    "                    if '$' in n and  n['$']:\n",
    "                        if check(l,i):\n",
    "                            res.extend([[k,index] for k in n['$']])\n",
    "                    if '#' in n and  n['#']:\n",
    "                        if check(l,i):\n",
    "                            res.extend([[k,index] for k in n['#'] if k!=index])\n",
    "                    break\n",
    "                else:\n",
    "                    if '#' in n and n['#']:\n",
    "                        if check(l,i):\n",
    "                            res.extend([[k,index] for k in n['#']])\n",
    "                    if l[i] not in n:\n",
    "                        break\n",
    "                    n = n[l[i]]\n",
    "                    i+=1\n",
    "            return res \n",
    "\n",
    "        res = []\n",
    "\n",
    "        for idx,w in enumerate(words):\n",
    "            add(w,idx)\n",
    "\n",
    "        for idx,w in enumerate(words):\n",
    "            res.extend(search(w[-1::-1],idx))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.index = []\n",
    "        self.val = None\n",
    "        self.next = []\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def huiwen(word):\n",
    "            n = len(word) // 2\n",
    "            for i in range(n):\n",
    "                if word[i] != word[-(i + 1)]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def pipei(word):\n",
    "            now = root\n",
    "            for c in word:\n",
    "                flag = False\n",
    "                for node in now.next:\n",
    "                    if node.val == c:\n",
    "                        flag = True\n",
    "                        now = node\n",
    "                        break\n",
    "                if not flag:\n",
    "                    return []\n",
    "            return now.index\n",
    "\n",
    "\n",
    "        root = Node()\n",
    "        zero = []\n",
    "        ret = []\n",
    "        for i, word in enumerate(words):\n",
    "            if not word:\n",
    "                zero.append(i)\n",
    "                continue\n",
    "\n",
    "            now = root\n",
    "            for c in word:\n",
    "                flag = False\n",
    "                for node in now.next:\n",
    "                    if node.val == c:\n",
    "                        now = node\n",
    "                        flag = True\n",
    "                        break\n",
    "                if not flag:\n",
    "                    tmp = Node()\n",
    "                    tmp.val = c\n",
    "                    now.next.append(tmp)\n",
    "                    now = tmp\n",
    "            now.index.append(i)\n",
    "        for i in range(len(zero) - 1):\n",
    "            for j in range(i + 1, len(zero)):\n",
    "                ret.append([i, j])\n",
    "                ret.append([j, i])\n",
    "\n",
    "        for i, word in enumerate(words):\n",
    "            if not word:\n",
    "                continue\n",
    "            if huiwen(word):\n",
    "                for j in zero:\n",
    "                    ret.append([i, j])\n",
    "                    ret.append([j, i])\n",
    "            for index in pipei(word[::-1]):\n",
    "                if index != i:\n",
    "                    ret.append([index, i])\n",
    "\n",
    "            for j in range(1, len(word)):\n",
    "                if huiwen(word[:j]):\n",
    "                    for index in pipei(word[j:][::-1]):\n",
    "                        if index != i:\n",
    "                            #print(1)\n",
    "                            ret.append([index, i])\n",
    "                #length = len(word)\n",
    "                #print(word[length - j:])           \n",
    "                if huiwen(word[-j:]):\n",
    "\n",
    "                    for index in pipei(word[:-j][::-1]):\n",
    "                        if index != i:\n",
    "                            #print(2)\n",
    "                            ret.append([i, index])\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children={}\n",
    "        self.index=-1\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        root=Trie()\n",
    "        n=len(words)\n",
    "        for i in range(n):\n",
    "            node=root\n",
    "            for s in words[i]:\n",
    "                if not s in node.children:\n",
    "                    node.children[s]=Trie()\n",
    "                node=node.children[s]\n",
    "            node.index=i\n",
    "        def search(left,right):\n",
    "            node=root\n",
    "            for i in range(right,left-1,-1):\n",
    "                if not word[i] in node.children:\n",
    "                    return -1\n",
    "                node=node.children[word[i]]\n",
    "            return node.index\n",
    "        def ispa(left,right):\n",
    "            left_index=left\n",
    "            right_index=right\n",
    "            while left_index < right_index:\n",
    "                if not word[left_index]==word[right_index]:\n",
    "                    return False\n",
    "                left_index+=1\n",
    "                right_index-=1\n",
    "            return True\n",
    "        ans=[]\n",
    "        for i in range(n):\n",
    "            word=words[i]\n",
    "            m=len(word)\n",
    "            for j in range(m+1):\n",
    "                if j and ispa(0,j-1):\n",
    "                    k=search(j,m-1)\n",
    "                    if k>-1 and k!= i:\n",
    "                        ans.append([k,i])\n",
    "                if ispa(j,m-1):\n",
    "                    k=search(0,j-1)\n",
    "                    if k>-1 and k!= i:\n",
    "                        ans.append([i,k])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = defaultdict(Node)\n",
    "        self.idx = -1\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "        self.idx = -1\n",
    "    \n",
    "    def insert(self, word, idx):\n",
    "        cur = self.root\n",
    "        for ch in word:\n",
    "            cur = cur.children[ch]\n",
    "        cur.idx = idx\n",
    "\n",
    "    def find(self, word):\n",
    "        cur = self.root\n",
    "        for ch in word:\n",
    "            if ch in cur.children:\n",
    "                cur = cur.children[ch]\n",
    "            else:\n",
    "                return -1\n",
    "        return cur.idx\n",
    "\n",
    "    def find(self, word, left, right):\n",
    "        # print(\"Find: \", word, left, right, word[left:right+1], word[right:left-1:-1])\n",
    "        cur = self.root\n",
    "        # for ch in word[right:left-1:-1]:\n",
    "        for i in range(right, left-1, -1):\n",
    "            ch = word[i]\n",
    "            if ch in cur.children:\n",
    "                cur = cur.children[ch]\n",
    "            else:\n",
    "                return -1\n",
    "        # print(\"=\", cur.idx)\n",
    "        return cur.idx\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "\n",
    "        def check(word, i, j):\n",
    "            if i>j:\n",
    "                return True\n",
    "            while i < j and word[i] == word[j]:\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return i>=j\n",
    "        \n",
    "        tree = Trie()\n",
    "        for i, w in enumerate(words):\n",
    "            tree.insert(w, i)\n",
    "        ans = []\n",
    "        for i, word in enumerate(words):\n",
    "            m = len(word)\n",
    "            for j in range(m + 1):\n",
    "                if check(word, j, m - 1):\n",
    "                    leftId = tree.find(word, 0, j - 1)\n",
    "                    if leftId != -1 and leftId != i:\n",
    "                        ans.append([i, leftId])\n",
    "                # else:\n",
    "                #     print(\"check False:\", word[j:m])\n",
    "                if j and check(word, 0, j - 1):\n",
    "                    rightId = tree.find(word, j, m - 1)\n",
    "                    if rightId != -1 and rightId != i:\n",
    "                        ans.append([rightId, i])\n",
    "                # else:\n",
    "                #     print(\"check False:\", word[0:j])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie():\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.child = [None]*26\n",
    "        self.is_end = False\n",
    "        self.numb = -1\n",
    "\n",
    "\n",
    "    def insert(self,word,number):\n",
    "        node = self\n",
    "        for i in word:\n",
    "            num = ord(i) - ord('a')\n",
    "            if node.child[num] == None:\n",
    "                node.child[num] = Trie()\n",
    "            node = node.child[num]\n",
    "        node.is_end = True\n",
    "        node.numb = number\n",
    "\n",
    "\n",
    "    def find(self,target):\n",
    "        node = self\n",
    "        for i in target:\n",
    "            num = ord(i) - ord('a')\n",
    "            if node.child[num] == None:\n",
    "                return False,-1\n",
    "            node = node.child[num]\n",
    "        return node.is_end == True , node.numb\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "\n",
    "        ##check 函数用于检验当前的字符串是否为回文字符串\n",
    "        def check(s): \n",
    "            left  = 0\n",
    "            right = len(s) - 1\n",
    "            while left < right:\n",
    "                if s[left] == s[right]:\n",
    "                    right -= 1\n",
    "                    left  += 1\n",
    "                else:\n",
    "                    return False\n",
    "            return True \n",
    "\n",
    "        T = Trie()\n",
    "        for i,word in enumerate (words):\n",
    "            T.insert(word,i)\n",
    "        ##首先构造一个字典树\n",
    "        ans = []\n",
    "        for i,word in enumerate (words):\n",
    "            m = len(word)\n",
    "            for j in range (0,m+1):\n",
    "                l_0 = word[:j]\n",
    "                l_1 = word[j:]\n",
    "                if check(l_1):\n",
    "                    mark,num = T.find(l_0[::-1])\n",
    "                    if mark and num != i:\n",
    "                        ans.append([i,num])\n",
    "                if j>0 and check(l_0):\n",
    "                    mark,num = T.find(l_1[::-1])\n",
    "                    if j > 0 and mark and num != i:\n",
    "                        ans.append([num,i])\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def check(s):\n",
    "            L = 0\n",
    "            R = len(s) - 1\n",
    "            while L < R and s[L] == s[R]:\n",
    "                L += 1\n",
    "                R -= 1\n",
    "            if L < R:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        def dfs(t, s):\n",
    "            for c in t:\n",
    "                if c == '#':\n",
    "                    if check(s):\n",
    "                        self.idx.extend(t['#'])\n",
    "                else:\n",
    "                    dfs(t[c], s + c)\n",
    "        tree1 = {}\n",
    "        tree2 = {}\n",
    "        for j in range(len(words)):\n",
    "            s = words[j]\n",
    "            t = tree1\n",
    "            for i in s:\n",
    "                if i not in t:\n",
    "                    t[i] = {}\n",
    "                t = t[i]\n",
    "            if '#' not in t:\n",
    "                t['#'] = []\n",
    "            t['#'].append(j)\n",
    "            t = tree2\n",
    "            for i in range(len(s) - 1, -1, -1):\n",
    "                if s[i] not in t:\n",
    "                    t[s[i]] = {}\n",
    "                t = t[s[i]]\n",
    "            if '#' not in t:\n",
    "                t['#'] = []\n",
    "            t['#'].append(j)\n",
    "        res = []\n",
    "        for i in range(len(words)):\n",
    "            t1 = tree1\n",
    "            t2 = tree2\n",
    "            s = words[i]\n",
    "            for j in s:\n",
    "                if j in t2:\n",
    "                    t2 = t2[j]\n",
    "                    t1 = t1[j]\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                self.idx = []\n",
    "                dfs(t2, '')\n",
    "                for j in self.idx:\n",
    "                    if i != j:\n",
    "                        res.append([i, j])\n",
    "            t1 = tree1\n",
    "            t2 = tree2\n",
    "            for j in s[::-1]:\n",
    "                if j in t1:\n",
    "                    t2 = t2[j]\n",
    "                    t1 = t1[j]\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                self.idx = []                \n",
    "                dfs(t1, '')\n",
    "                for j in self.idx:\n",
    "                    if i != j and words[i] != words[j][::-1]:\n",
    "                        res.append([j, i])\n",
    "        return res                    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def trieNode():\n",
    "            return defaultdict(trieNode)\n",
    "        def makeTrie(itWords):\n",
    "            trie = defaultdict(trieNode)\n",
    "            for idx, w in itWords:\n",
    "                node = trie\n",
    "                for c in w:\n",
    "                    node = node[c]\n",
    "                node[None] = idx\n",
    "            return trie\n",
    "        def dfs(node, stack):\n",
    "            for k, v in node.items():\n",
    "                if k is None:\n",
    "                    half = len(stack)>>1\n",
    "                    if stack[:half] == stack[:-half-1:-1]:\n",
    "                        yield [list(stack), v]\n",
    "                    continue\n",
    "                stack.append(k)\n",
    "                yield from dfs(v, stack)\n",
    "                stack.pop()\n",
    "            \n",
    "        def findPairs(trie, itWords, rev=False):\n",
    "            stack = []\n",
    "            for i, word in itWords:\n",
    "                node = trie\n",
    "                for c in word:\n",
    "                    node = node.get(c)\n",
    "                    if not node: break\n",
    "                if node:\n",
    "                    for seq, j in dfs(node, stack):\n",
    "                        if i != j:\n",
    "                            yield ((i, j) if rev else (j, i))\n",
    "\n",
    "        posTrie = makeTrie(enumerate(words))\n",
    "        # print(posTrie)\n",
    "        negWords = ((i, reversed(w)) for i, w in enumerate(words))\n",
    "        result = set(findPairs(posTrie, negWords))\n",
    "\n",
    "        negTrie = makeTrie((i, reversed(w)) for i, w in enumerate(words))\n",
    "        posWords = enumerate(words)\n",
    "        result.update(findPairs(negTrie, posWords, rev=True))\n",
    "        return list(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 暴力（超时）\n",
    "# class Solution:\n",
    "#     def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "#         n = len(words)\n",
    "#         ans = []\n",
    "#         for i in range(n):\n",
    "#             for j in range(n):\n",
    "#                 if i!=j:\n",
    "#                     word = words[i]+words[j]\n",
    "#                     if word==word[::-1]:\n",
    "#                         ans.append([i,j])\n",
    "#         return ans\n",
    "\n",
    "# 哈希表\n",
    "# class Solution:\n",
    "#     def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "#         def is_palindrome(word,l,r):\n",
    "#             n = r-l+1\n",
    "#             return n<=1 or all(word[l+i]==word[l+n-i-1] for i in range(n//2))\n",
    "\n",
    "#         n = len(words)\n",
    "#         ans = []\n",
    "#         worddict = {word:i for i,word in enumerate(words)}\n",
    "#         for i,word in enumerate(words):\n",
    "#             m = len(word)\n",
    "#             for k in range(m+1):\n",
    "#                 prefix,suffix = word[:k][::-1],word[m-k:][::-1]\n",
    "#                 if prefix in worddict and i!=worddict[prefix] and is_palindrome(word,k,m-1):\n",
    "#                     ans.append([i,worddict[prefix]])\n",
    "#                 if k<m and suffix in worddict and i!=worddict[suffix] and is_palindrome(word,0,m-k-1):  # k<m避免镜像单词导致重复\n",
    "#                     ans.append([worddict[suffix],i])\n",
    "#         return ans\n",
    "\n",
    "# class Solution:\n",
    "#     def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "#         def is_palindrome(word):\n",
    "#             return word==word[::-1]  # 切片快于循环\n",
    "\n",
    "#         n = len(words)\n",
    "#         ans = []\n",
    "#         worddict = {word:i for i,word in enumerate(words)}\n",
    "#         for i,word in enumerate(words):\n",
    "#             m = len(word)\n",
    "#             for k in range(m+1):\n",
    "#                 prefix,suffix = word[:k][::-1],word[m-k:][::-1]\n",
    "#                 if prefix in worddict and i!=worddict[prefix] and is_palindrome(word[k:]):\n",
    "#                     ans.append([i,worddict[prefix]])\n",
    "#                 if k<m and suffix in worddict and i!=worddict[suffix] and is_palindrome(word[:m-k]):  # k<m避免镜像单词导致重复\n",
    "#                     ans.append([worddict[suffix],i])\n",
    "#         return ans\n",
    "\n",
    "# Trie树\n",
    "# class Solution:\n",
    "#     def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "#         def insert(word,i):\n",
    "#             node = trie\n",
    "#             for c in word:\n",
    "#                 node = node.setdefault(c,{})\n",
    "#             node['#'] = i\n",
    "        \n",
    "#         def is_palindrome(word,l,r):\n",
    "#             n = r-l+1\n",
    "#             return n<=1 or all(word[l+i]==word[l+n-i-1] for i in range(n//2))\n",
    "        \n",
    "#         def search(word,l,r):\n",
    "#             node = trie\n",
    "#             word = word[l:r+1][::-1]  # 不切片，采用下标访问会超时\n",
    "#             for c in word:\n",
    "#                 if c in node:\n",
    "#                     node = node[c]\n",
    "#                 else:\n",
    "#                     return -1\n",
    "#             return node.get('#',-1)\n",
    "\n",
    "#         n = len(words)\n",
    "#         ans = []\n",
    "#         trie = {}\n",
    "#         for i,word in enumerate(words):\n",
    "#             insert(word,i)\n",
    "#         for i,word in enumerate(words):\n",
    "#             m = len(word)\n",
    "#             for k in range(m+1):\n",
    "#                 preid,sufid = search(word,0,k-1),search(word,m-k,m-1)\n",
    "#                 if preid!=-1 and i!=preid and is_palindrome(word,k,m-1):\n",
    "#                     ans.append([i,preid])\n",
    "#                 if k<m and sufid!=-1 and i!=sufid and is_palindrome(word,0,m-k-1):  # k<m避免镜像单词导致重复\n",
    "#                     ans.append([sufid,i])\n",
    "#         return ans\n",
    "\n",
    "# class Solution:\n",
    "#     def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "#         def insert(trie,word,i):\n",
    "#             node = trie\n",
    "#             for c in word:\n",
    "#                 node = node.setdefault(c,{})\n",
    "#             node['#'] = i\n",
    "\n",
    "#         def is_palindrome(word):\n",
    "#             return word==word[::-1]  # 切片快于循环\n",
    "\n",
    "#         n = len(words)\n",
    "#         ans = []\n",
    "#         prefix,suffix,word2idx = {},{},{}\n",
    "#         for i,word in enumerate(words):\n",
    "#             insert(prefix,word,i)\n",
    "#             insert(suffix,word[::-1],i)\n",
    "#             word2idx[word] = i\n",
    "#         for i,word in enumerate(words):\n",
    "#             node = prefix\n",
    "#             for c in reversed(word):\n",
    "#                 if '#' in node:\n",
    "#                     j = node['#']\n",
    "#                     if i!=j and is_palindrome(word[:len(word)-len(words[j])]):\n",
    "#                         ans.append([j,i])\n",
    "#                 if c in node:\n",
    "#                     node = node[c]\n",
    "#                 else:\n",
    "#                     break\n",
    "#             node = suffix\n",
    "#             for c in word:\n",
    "#                 if '#' in node:\n",
    "#                     j = node['#']\n",
    "#                     if i!=j and is_palindrome(word[len(words[j]):]):\n",
    "#                         ans.append([i,j])\n",
    "#                 if c in node:\n",
    "#                     node = node[c]\n",
    "#                 else:\n",
    "#                     break\n",
    "#             revword = word[::-1]\n",
    "#             if revword in word2idx:\n",
    "#                 j = word2idx[revword]\n",
    "#                 if i!=j:\n",
    "#                     ans.append([i,j])\n",
    "#         return ans\n",
    "\n",
    "# Trie树+Manacher算法\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def manacher(word):\n",
    "            prefix = [False]*(len(word)+1)\n",
    "            suffix = [False]*(len(word)+1)\n",
    "            s = '#'+'#'.join(word)+'#'\n",
    "            n = len(s)\n",
    "            radius = [1]*n\n",
    "            r_max,i_max = 0,0\n",
    "            for i in range(n):\n",
    "                if i>=r_max:\n",
    "                    r_max = i_max = i\n",
    "                radius[i] = min(radius[2*i_max-i],r_max-i+1)\n",
    "                while i-radius[i]>=0 and i+radius[i]<n and s[i+radius[i]]==s[i-radius[i]]:\n",
    "                    radius[i] += 1\n",
    "                if i+radius[i]-1>r_max:\n",
    "                    r_max = i+radius[i]-1\n",
    "                    i_max = i\n",
    "                if i-radius[i]+1 == 0:\n",
    "                    prefix[radius[i]-1] = True\n",
    "                if i+radius[i] == n:\n",
    "                    suffix[radius[i]-1] = True\n",
    "            return prefix,suffix\n",
    "\n",
    "        def insert(trie,word,i):\n",
    "            node = trie\n",
    "            for c in word:\n",
    "                node = node.setdefault(c,{})\n",
    "            node['#'] = i\n",
    "        \n",
    "        def query(trie,word):\n",
    "            node = trie\n",
    "            ans = []\n",
    "            for c in word:\n",
    "                if '#' in node:\n",
    "                    ans.append(node['#'])\n",
    "                if c not in node:\n",
    "                    return ans\n",
    "                node = node[c]\n",
    "            if '#' in node:\n",
    "                ans.append(node['#'])\n",
    "            return ans\n",
    "\n",
    "        n = len(words)\n",
    "        ans = []\n",
    "        prefix,suffix = {},{}\n",
    "        prefix_palindrome,suffix_palindrome = [None]*n,[None]*n\n",
    "        for i,word in enumerate(words):\n",
    "            insert(prefix,word,i)\n",
    "            insert(suffix,word[::-1],i)\n",
    "            prefix_palindrome[i],suffix_palindrome[i] = manacher(word)\n",
    "        for i,word in enumerate(words):\n",
    "            preifx_id = query(prefix,word[::-1])\n",
    "            suffix_id = query(suffix,word)\n",
    "            for j in preifx_id:\n",
    "                if i!=j and prefix_palindrome[i][len(word)-len(words[j])]:\n",
    "                    ans.append([j,i])\n",
    "            for j in suffix_id:\n",
    "                if len(word)!=len(words[j]) and i!=j and suffix_palindrome[i][len(word)-len(words[j])]:\n",
    "                    ans.append([i,j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "MOD = 10 ** 11 + 7\n",
    "\n",
    "\n",
    "@cache\n",
    "def getNumFromS(i):\n",
    "    return ord(i) - ord('a') + 1\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        n = len(words)\n",
    "\n",
    "        base = len(set(''.join(words)))\n",
    "        \n",
    "        @cache\n",
    "        def getHashStr(s):\n",
    "            if not s: return 0\n",
    "            seq = 0\n",
    "            for i in s:\n",
    "                seq = (seq * base + getNumFromS(i)) % MOD\n",
    "            return seq\n",
    "        \n",
    "        def append(res, li, index, rev = False):\n",
    "            for preIndex in li:\n",
    "                if preIndex == index: continue\n",
    "                if rev:\n",
    "                    res.add((index, preIndex))\n",
    "                else:\n",
    "                    res.add((preIndex, index))\n",
    "\n",
    "        def getAns(res, words, nn = False):\n",
    "            m = defaultdict(list)\n",
    "            for index, w in enumerate(words):\n",
    "                m[getHashStr(w)].append(index)\n",
    "\n",
    "            for index, w in enumerate(words):\n",
    "                wlen = len(w)\n",
    "                other = [None] * wlen\n",
    "                seq = 0\n",
    "                for Oindex, i in enumerate(reversed(w)):\n",
    "                    seq = (seq * base + getNumFromS(i)) % MOD\n",
    "                    other[wlen - Oindex - 1] = seq\n",
    "                \n",
    "                seq = rev = 0\n",
    "                mi = 1\n",
    "                for wIndex, i in enumerate(w):\n",
    "                    seq = (seq * base + getNumFromS(i)) % MOD\n",
    "                    rev = (getNumFromS(i) * mi + rev) % MOD\n",
    "                    mi = (mi * base) % MOD\n",
    "                    if seq == rev:\n",
    "                        if wIndex == wlen - 1 or seq != rev: continue\n",
    "                        append(res, m[other[wIndex + 1]], index, nn)\n",
    "                if seq == rev:\n",
    "                    append(res, m[0], index, nn)\n",
    "                append(res, m[rev], index, nn)\n",
    "\n",
    "            return res\n",
    "                        \n",
    "        res = set()\n",
    "        getAns(res, words)\n",
    "        getAns(res, [''.join(reversed(i)) for i in words ], True)\n",
    " \n",
    "        del getHashStr\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        n = len(words)\n",
    "        prefixParlindromeArr = [[] for i in range(n)]\n",
    "        suffixParlindromeArr = [[] for i in range(n)]\n",
    "        for wordIdx,word in enumerate(words):\n",
    "            prefixParlindromeArr[wordIdx] = [0] * len(word)\n",
    "            suffixParlindromeArr[wordIdx] = [0] * len(word)\n",
    "            s = word\n",
    "            s = '#' + '#'.join(list(s)) + '#'\n",
    "            arm_len = []\n",
    "            right = -1\n",
    "            j = -1\n",
    "            for i in range(len(s)):\n",
    "                if right >= i:\n",
    "                    i_sym = 2 * j - i\n",
    "                    min_arm_len = min(arm_len[i_sym], right - i)\n",
    "                    cur_arm_len = self.expand(s, i - min_arm_len, i + min_arm_len)\n",
    "                else:\n",
    "                    cur_arm_len = self.expand(s, i, i)\n",
    "                arm_len.append(cur_arm_len)\n",
    "                if i + cur_arm_len > right:\n",
    "                    j = i\n",
    "                    right = i + cur_arm_len\n",
    "                start = i - cur_arm_len\n",
    "                end = i + cur_arm_len\n",
    "                if (start + 1 == 1 and end > 0):\n",
    "                    prefixParlindromeArr[wordIdx][(end - 1) // 2] = 1\n",
    "                if (end + 1 == len(s) and start != end):\n",
    "                    suffixParlindromeArr[wordIdx][start // 2] = 1\n",
    "        trieTree = self.trieTree(words)\n",
    "        rtn = []\n",
    "        for wordIdx,word in enumerate(words):\n",
    "            n = len(word)\n",
    "            treeNode = trieTree\n",
    "            end = True\n",
    "            for j in range(n - 1, -1 ,-1):\n",
    "                ch = word[j]\n",
    "                chIdx = ord(ch) - ord('a')\n",
    "                if (treeNode[26] > 0 and treeNode[26] - 1 != wordIdx):\n",
    "                    # print(wordIdx, treeNode[26] - 1,j, prefixParlindromeArr[wordIdx])\n",
    "                    if (prefixParlindromeArr[wordIdx][j] == 1):\n",
    "                        # print([treeNode[26] - 1, wordIdx])\n",
    "                        rtn.append([treeNode[26] - 1, wordIdx])\n",
    "                if (0 == treeNode[chIdx]):\n",
    "                    end = False\n",
    "                    break\n",
    "                treeNode = treeNode[chIdx]\n",
    "            # print(wordIdx,treeNode[26])\n",
    "            \n",
    "            if (not end):\n",
    "                continue\n",
    "            for preWordIdx,pos in treeNode[27]:\n",
    "                if (wordIdx == 2):\n",
    "                    print(treeNode[27])\n",
    "                # print(wordIdx,preWordIdx,pos,treeNode[26])\n",
    "                if (preWordIdx == wordIdx):\n",
    "                    continue\n",
    "                if (treeNode[26] - 1 == preWordIdx):\n",
    "                    rtn.append([preWordIdx, wordIdx])\n",
    "                else:\n",
    "                    # print(wordIdx,preWordIdx,pos,suffixParlindromeArr[0][1])\n",
    "                    if (suffixParlindromeArr[preWordIdx][pos + 1] == 1):\n",
    "                        rtn.append([preWordIdx, wordIdx])\n",
    "        return rtn\n",
    "    def expand(self, s, left, right):\n",
    "        while left >= 0 and right < len(s) and s[left] == s[right]:\n",
    "            left -= 1\n",
    "            right += 1\n",
    "        return (right - left - 2) // 2\n",
    "    def trieTree(self, words):\n",
    "        trieTree = [0] * 28\n",
    "        trieTree[27] = []\n",
    "        for i,word in enumerate(words):\n",
    "            treeNode = trieTree\n",
    "            treeNode[27].append((i,-1))\n",
    "            for j,ch in enumerate(word):\n",
    "                chIdx = ord(ch) - ord('a')\n",
    "                if (0 == treeNode[chIdx]):\n",
    "                    treeNode[chIdx] = [0] * 28\n",
    "                    treeNode[chIdx][27] = []\n",
    "                treeNode = treeNode[chIdx]\n",
    "                treeNode[27].append((i,j))\n",
    "            treeNode[26] = i + 1\n",
    "        return trieTree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "\n",
    "    def __init__(self):\n",
    "        self.lookup = {}\n",
    "\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        tree = self.lookup\n",
    "\n",
    "        for s in word:\n",
    "            if s not in tree:\n",
    "                tree[s] = {}\n",
    "            tree = tree[s]\n",
    "        tree['#'] = '#'\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        tree = self.lookup\n",
    "        for s in word:\n",
    "            if s not in tree:\n",
    "                return False\n",
    "            tree = tree[s]\n",
    "        if '#' in tree:\n",
    "            return True\n",
    "\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "class Solution:\n",
    "    def get_palindrome_parts(self,str):\n",
    "        pre,suf = [],[]\n",
    "        lenstr = len(str)\n",
    "\n",
    "        for i in range(0,lenstr + 1):\n",
    "            if str[:i] == str[:i][::-1]:\n",
    "                pre.append(str[i:][::-1])\n",
    "\n",
    "            if str[i:] == str[i:][::-1]:\n",
    "                suf.append(str[:i][::-1])\n",
    "\n",
    "        return pre, suf\n",
    "\n",
    "\n",
    "    def palindromePairs(self, words):\n",
    "        tree = Trie()\n",
    "        for w in words:\n",
    "            tree.insert(w)\n",
    "        dataset = {w:i for i,w in enumerate(words)}\n",
    "        res = []\n",
    "\n",
    "        for index, word in enumerate(words):\n",
    "            pre, suf = self.get_palindrome_parts(word)\n",
    "\n",
    "            for p in pre:\n",
    "                if p in dataset and index != dataset[p] and p[::-1] != word:\n",
    "                    res.append([dataset[p],index])\n",
    "            \n",
    "            for s in suf:\n",
    "                if s in dataset  and index != dataset[s]:\n",
    "                    res.append([index, dataset[s]])\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    方案1: 所有的ij对，检查回文，假设单词长度为K, 个数为N, 那么时间复杂度为O(K*N**2)\n",
    "\n",
    "    方案2: 翻转所有的单词，O(N*K)时间 + O(N*K)空间\n",
    "          对每个单词，自己为左端，查找中心为空，或中心为重复字符的剩余， 可以重复1到m次，m为中间重复字符的个数O(K)\n",
    "          如果A, B两个单词，如果len(A)>len(B)那么 中心回文串在A的左边或者右边(或者是逆序的左边)\n",
    "          检查A的所有长度的逆序\n",
    "          O(N*K**2)\n",
    "\n",
    "    方案3:\n",
    "          **不只是是重复，中心是回文串**\n",
    "\n",
    "    方案4:\n",
    "         字典树（Trie树）\n",
    "         O(N*K*K), 判断中间是回文需要O(K*K)\n",
    "\n",
    "\n",
    "    \"\"\"\n",
    "\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        word2rev_word = {word: \"\".join(reversed(word)) for i, word in enumerate(words)}\n",
    "        rev_word2i = {\"\".join(reversed(word)): i for i, word in enumerate(words) if word}\n",
    "        word2i = {word: i for i, word in enumerate(words) if word}\n",
    "        min_len = min(len(word) for word in word2i)\n",
    "        ans = []\n",
    "        for word in word2i:\n",
    "            # 以word作为左端，并且中心在左端的回文对\n",
    "            # 中心在右端的情况 等价于 单词的逆序中心在左端，并在单词的逆序中查找右端\n",
    "            # 1. 中心为空的情况\n",
    "            i = word2i[word]\n",
    "            rev_word = word2rev_word[word]\n",
    "            if rev_word in word2i:\n",
    "                j = word2i[rev_word]\n",
    "                if i != j:\n",
    "                    ans.append([i, j])\n",
    "            # 2. 中心在左边并且是重复字符的情况\n",
    "            # O(K*K)\n",
    "            # 单词的所有前缀，O(K)及前缀的逆序O(K)\n",
    "            for r in range(len(word) - 1, 0, -1):\n",
    "                _mid = word[r:]\n",
    "                if self.is_palindrome(_mid):\n",
    "                    rest = word[:r]\n",
    "                    if len(rest) < min_len:\n",
    "                        break\n",
    "                    rev_rest = \"\".join(reversed(rest))\n",
    "                    if rev_rest in word2i:\n",
    "                        j = word2i[rev_rest]\n",
    "                        if i != j:\n",
    "                            ans.append([i, j])\n",
    "            # 中心在右边 <=> 等价于单词翻转过后，中心在左边的情况\n",
    "        for rev_word in rev_word2i:\n",
    "            # 1. 中心为空的情况，不需要考虑因为以及考虑过了\n",
    "            # 2. 中心在左边并且是重复字符的情况\n",
    "            j = rev_word2i[rev_word]\n",
    "            for r in range(len(rev_word) - 1, 0, -1):\n",
    "                _mid = rev_word[r:]\n",
    "                # if rev_word == \"\".join(reversed(\"abaabaa\")):\n",
    "                #     print(rev_word, _mid, rev_word[:r])\n",
    "                if self.is_palindrome(_mid):\n",
    "                    rest = rev_word[:r]\n",
    "                    if len(rest) < min_len:\n",
    "                        break\n",
    "                    rev_rest = \"\".join(reversed(rest))\n",
    "                    if rev_rest in rev_word2i:\n",
    "                        i = rev_word2i[rev_rest]\n",
    "                        if i != j:\n",
    "                            ans.append([i, j])\n",
    "        # 处理特殊情况, 空字符，左右两边都可以O(N*K)\n",
    "        i_empty_word = None\n",
    "        for i, word in enumerate(words):\n",
    "            if not word:\n",
    "                i_empty_word = i\n",
    "        if i_empty_word is not None:\n",
    "            for j, word in enumerate(words):\n",
    "                if word and self.is_palindrome(word):\n",
    "                    ans.append([i_empty_word, j])\n",
    "                    ans.append([j, i_empty_word])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "    @lru_cache(maxsize=None)\n",
    "    def is_palindrome(self, word):\n",
    "        # word不是空\n",
    "        start, end = 0, len(word) - 1\n",
    "        while start < end:\n",
    "            if word[start] == word[end]:\n",
    "                start += 1\n",
    "                end -= 1\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 11 + 7\n",
    "\n",
    "@cache\n",
    "def getNumFromS(i):\n",
    "    if not i: return -1\n",
    "    return ord(i) - ord('a') + 1\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "\n",
    "        base = 26\n",
    "\n",
    "        @cache\n",
    "        def reverS(i: str):\n",
    "            return ''.join(reversed(i))\n",
    "\n",
    "        \n",
    "        @cache\n",
    "        def getHandleStr(s):\n",
    "            if not s: return -1\n",
    "            seq = 0\n",
    "            for index, i in enumerate(s):\n",
    "                n = getNumFromS(i)\n",
    "                seq = (seq * base + n) % MOD\n",
    "            return seq \n",
    "\n",
    "        @cache\n",
    "        def handle(s: str):\n",
    "            if not s: return []\n",
    "            seq = rev = 0\n",
    "            mi = 1\n",
    "            res = []\n",
    "            for index, i in enumerate(s):\n",
    "                n = getNumFromS(i)\n",
    "                rev = (n * mi + rev) % MOD\n",
    "                seq = (seq * base + n) % MOD\n",
    "                mi *= base\n",
    "                if seq == rev: res.append(index)\n",
    "\n",
    "            if not res: return [-1]\n",
    "            rev = [0] * len(s)\n",
    "            seq = 0\n",
    "            for index, i in enumerate(reversed(s)):\n",
    "                n = getNumFromS(i)\n",
    "                seq = (seq * base + n) % MOD\n",
    "                rev[len(s) - index - 1] = seq\n",
    "            res = [rev[i + 1] if i + 1 < len(s) else -1 for i in res]\n",
    "            res.append(rev[0])\n",
    "            return res\n",
    "\n",
    "\n",
    "        def getAns(words: List[str], r = False):\n",
    "            res = set()\n",
    "            m = defaultdict(list)\n",
    "            for index, i in enumerate(words):\n",
    "                m[getHandleStr(i)].append(index)\n",
    "            \n",
    "            for index, i in enumerate(words):\n",
    "                for key in handle(i):\n",
    "                    for preIndex in m[key]:\n",
    "                        if index == preIndex: continue\n",
    "                        if r:\n",
    "                            res.add((index, preIndex))\n",
    "                        else:\n",
    "                            res.add((preIndex, index))\n",
    "            return res\n",
    "\n",
    "\n",
    "        res1 = getAns(words)\n",
    "        res2 = getAns([reverS(i) for i in words], True)\n",
    "        res1.update(res2)\n",
    "\n",
    "        del getHandleStr\n",
    "        del handle\n",
    "\n",
    "        return list(res1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words):\n",
    "        dic = {}\n",
    "        end = \"#\"\n",
    "        for i in range(len(words)):\n",
    "            word = words[i]\n",
    "            current = dic\n",
    "            for j in word[::-1]:\n",
    "                if j not in current:\n",
    "                    current[j] = {}\n",
    "                current = current[j]\n",
    "            current[end] = i\n",
    "        print(dic)\n",
    "        result = []\n",
    "        for i in range(len(words)):\n",
    "            word = words[i]\n",
    "            current = dic\n",
    "            exists = True\n",
    "            for j in range(len(word)):\n",
    "                if end in current:\n",
    "                    rest = word[j:]\n",
    "                    if rest == rest[::-1]:\n",
    "                        result.append([i, current[end]])\n",
    "                if word[j] not in current:\n",
    "                    exists = False\n",
    "                    break\n",
    "                current = current[word[j]]\n",
    "            if exists:\n",
    "                for k in self.findEnd(current, \"\"):\n",
    "                    if k != i:\n",
    "                        result.append([i, k])\n",
    "        return result\n",
    "\n",
    "    def findEnd(self, dic, prefix):\n",
    "        end = \"#\"\n",
    "        result = []\n",
    "        for i in dic.keys():\n",
    "            if i == end:\n",
    "                if prefix == prefix[::-1]:\n",
    "                    result.append(dic[i])\n",
    "            else:\n",
    "                result.extend(self.findEnd(dic[i], prefix+i))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.end = 0\n",
    "        self.children = {}\n",
    "        self.suffix = []\n",
    "        \n",
    "    def addWord(self, word, i, idx = 0):\n",
    "        self.suffix.append(i)\n",
    "        if idx == len(word):\n",
    "            self.end = i\n",
    "            return\n",
    "        if word[idx] not in self.children:\n",
    "            self.children[word[idx]] = Trie()\n",
    "        self.children[word[idx]].addWord(word, i, idx + 1)\n",
    "    \n",
    "    def getSuffix(self):\n",
    "        return self.suffix\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def same():\n",
    "            if len(words[0]) < 2:\n",
    "                return False\n",
    "            c = words[0][0]\n",
    "            for word in words:\n",
    "                if len(word) < 2:\n",
    "                    return False\n",
    "                if word[0] != c or word[-1] != c:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        n = len(words)\n",
    "        while same():\n",
    "            for i in range(n):\n",
    "                words[i] = words[i][1:-1]\n",
    "                \n",
    "                \n",
    "        @cache\n",
    "        def isPal(i, left, rev):\n",
    "            if rev:\n",
    "                word = words[i][::-1]\n",
    "            else:\n",
    "                word = words[i]\n",
    "            right = len(word) - 1\n",
    "            while left < right:\n",
    "                if word[left] != word[right]:\n",
    "                    return False\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "            \n",
    "        ori = Trie()\n",
    "        rev = Trie()\n",
    "        \n",
    "        for i, word in enumerate(words):\n",
    "            ori.addWord(word, i + 1)\n",
    "            rev.addWord(word[::-1], i + 1)\n",
    "            \n",
    "        ret = []\n",
    "            \n",
    "        def travel(o, r, idx):\n",
    "            if o.end:\n",
    "                for i in r.getSuffix():\n",
    "                    if i == r.end:\n",
    "                        continue\n",
    "                    if isPal(i - 1, idx + 1, True):\n",
    "                        ret.append([o.end - 1, i - 1])\n",
    "            if r.end:\n",
    "                for i in o.getSuffix():\n",
    "                    if i == o.end:\n",
    "                        continue\n",
    "                    if isPal(i - 1, idx + 1, False):\n",
    "                        ret.append([i - 1, r.end - 1])\n",
    "            if o.end and r.end and o.end != r.end:\n",
    "                ret.append([o.end - 1, r.end - 1])\n",
    "                \n",
    "            for c in o.children.keys():\n",
    "                if c in r.children:\n",
    "                    travel(o.children[c], r.children[c], idx + 1)\n",
    "            \n",
    "        travel(ori, rev, -1)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import zip_longest\n",
    "class Solution:\n",
    "\tdef palindromePairs(self,words):\n",
    "\t\ttry: null=words.index(\"\") #\"\"太特殊了 还是特殊处理比较方便\n",
    "\t\texcept:\tnull=-1\n",
    "\t\tdef manacher(s): #马拉车算法\n",
    "\t\t\tori_size=len(s) #字符串原本的长度\n",
    "\t\t\ts=\"{#\"+\"#\".join(s)+\"#}\" #变化字符串 马拉车算法实现的根基\n",
    "\t\t\tcur_size=len(s)\n",
    "\t\t\tp=[0]*(cur_size-1)\n",
    "\t\t\tId=Max=0\n",
    "\t\t\tfor i,c in enumerate(s[1:-1],1):\n",
    "\t\t\t\tif Max>i:\n",
    "\t\t\t\t\tp[i]=min(p[(Id<<1)-i],Max-i)\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tp[i]=1\n",
    "\t\t\t\twhile s[i-p[i]]==s[i+p[i]]: #上面虽然是马拉车的关键 但是这边也是不能少的 一开始我就是没注意这个所以死活没完全理解马拉车/(ㄒoㄒ)/~~\n",
    "\t\t\t\t\tp[i]+=1\n",
    "\t\t\t\tif p[i]+i>Max:\n",
    "\t\t\t\t\tId,Max=i,p[i]+i\n",
    "\t\t\treturn [n-1==i for i,n in enumerate(p[2:1+ori_size],1)] #前缀字符串是不是回文\n",
    "\t\tprefixTrie=dict() #创建一个前缀字典树\n",
    "\t\tfor i,word in enumerate(words):\n",
    "\t\t\ttmp,p=prefixTrie,manacher(word[::-1])\n",
    "\t\t\tfor char,flag in zip_longest(word,p[::-1],fillvalue=True):\n",
    "\t\t\t\ttmp=tmp.setdefault(char,{})\n",
    "\t\t\t\tif flag: #一定要注意这边的先后顺序 先tmp到下一层 然后再看flag\n",
    "\t\t\t\t\ttmp.setdefault(\"can\",[]).append(i)\n",
    "\t\t\ttmp[\"#\"]=i #字符串的结束标志\n",
    "\t\tans=[]\n",
    "\t\tfor i,word in enumerate(words):\n",
    "\t\t\ttmp,p=prefixTrie,manacher(word)\n",
    "\t\t\ttry:\n",
    "\t\t\t\tfor char,flag in zip_longest(word[::-1],p[::-1]):\n",
    "\t\t\t\t\ttmp=tmp[char]\n",
    "\t\t\t\t\tif flag and \"#\" in tmp:\n",
    "\t\t\t\t\t\tans.append([tmp[\"#\"],i])\n",
    "\t\t\t\tfor idx in tmp.get(\"can\",[]):\n",
    "\t\t\t\t\tif i==idx:\n",
    "\t\t\t\t\t\tif null!=-1:\n",
    "\t\t\t\t\t\t\tans+=[[null,i],[i,null]]\n",
    "\t\t\t\t\telse:\n",
    "\t\t\t\t\t\tans.append([idx,i])\n",
    "\t\t\texcept KeyError: #找不到匹配的路径了\n",
    "\t\t\t\tcontinue\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]: \n",
    "        @lru_cache(None)\n",
    "        def palindrome(ss:str) -> bool:\n",
    "            return ss==ss[::-1]\n",
    "        # end  : all words end by char 'x' \n",
    "        end = {}\n",
    "        # pal  : all palindrome word\n",
    "        pal = []\n",
    "        for i,word in enumerate(words):\n",
    "            # word is empty string\n",
    "            if word=='':\n",
    "                continue \n",
    "            # palindrome word\n",
    "            if palindrome(word):\n",
    "                pal.append(i)\n",
    "            b = word[-1]\n",
    "            if b in end:\n",
    "                end[b].append(i)\n",
    "            else:\n",
    "                end[b] = [i]\n",
    "        # 试试所有不同的开头\n",
    "        res = []\n",
    "        for i, word in enumerate(words):\n",
    "            # 如果word为空字符串\n",
    "            if word=='':\n",
    "                for j in pal:\n",
    "                    res.append([i,j])\n",
    "                    res.append([j,i])\n",
    "                continue \n",
    "            a = word[0]\n",
    "            if a not in end:\n",
    "                continue \n",
    "            for x in end[a]:\n",
    "                if i==x:\n",
    "                    continue\n",
    "                s2 = words[x]\n",
    "                if palindrome(word+s2):\n",
    "                    res.append([i,x])\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.neighbors = {}\n",
    "        self.flag = -1\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def palindromePairs(self, words):\n",
    "        \"\"\"\n",
    "        :type words: List[str]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        tree = Node('#')\n",
    "        out = []\n",
    "        for k, word in enumerate(words):\n",
    "            node = tree\n",
    "            for i in range(len(word)):\n",
    "                if word[i] not in node.neighbors:\n",
    "                    new_node = Node(word[i])\n",
    "                    node.neighbors[word[i]] = new_node\n",
    "                    node = new_node\n",
    "                else:\n",
    "                    node = node.neighbors[word[i]]\n",
    "            node.flag = k\n",
    "\n",
    "        def search(node, m, k):\n",
    "            if node.flag >= 0:\n",
    "                new_word = words[node.flag][m:]\n",
    "                if new_word == new_word[::-1]:\n",
    "                    out.append([node.flag, k])\n",
    "            for next_node in node.neighbors:\n",
    "                search(node.neighbors[next_node], m, k)\n",
    "\n",
    "        for k, word in enumerate(words):\n",
    "            m = len(word)\n",
    "            node = tree\n",
    "            i = 0\n",
    "            while i < m:\n",
    "                if node.flag >= 0:\n",
    "                    new_word = word[: m - i]\n",
    "                    if new_word == new_word[::-1]:\n",
    "                        out.append([node.flag, k])\n",
    "                if word[m - 1 - i] in node.neighbors:\n",
    "                    node = node.neighbors[word[m - 1 - i]]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "            if i == m:\n",
    "                if node.flag >= 0 and k != node.flag:\n",
    "                    out.append([node.flag, k])\n",
    "                for next_node in node.neighbors:\n",
    "                    search(node.neighbors[next_node], m, k)\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        tree = QZ_tree()\n",
    "        for i in range(len(words)):\n",
    "            tree.insert(words[i], i)\n",
    "        words_reverse = []\n",
    "        for i in range(len(words)):\n",
    "            words_reverse.append(words[i][::-1])\n",
    "        result = []\n",
    "        for i in range(len(words_reverse)):\n",
    "            j = 0\n",
    "            node = tree.root\n",
    "            while j < len(words_reverse[i]):\n",
    "                if node.end != None:\n",
    "                    if self.huiwen(words_reverse[i][j:]) and node.end != i:\n",
    "                        result.append([node.end, i])\n",
    "                if words_reverse[i][j] not in node.next.keys():\n",
    "                    break\n",
    "                node = node.next[words_reverse[i][j]]\n",
    "                j += 1\n",
    "            # if j == len(words_reverse[i]) and node.end != None and node.end != i:\n",
    "            #     result.append([node.end, i])\n",
    "            if j == len(words_reverse[i]):\n",
    "                huiwen_end = self.tree_huiwen(node)\n",
    "                # if i == 1:\n",
    "                #     print(node.next)\n",
    "                #     print(huiwen_end)\n",
    "                for huiwen_index in huiwen_end:\n",
    "                    if huiwen_index != i:\n",
    "                        result.append([huiwen_index, i])\n",
    "        return result\n",
    "\n",
    "    def get_str(self, root, strs, result): #得到这个根节点之后的所有字符串\n",
    "        if root.end != None:\n",
    "            result.append((strs[:], root.end))\n",
    "        node = root\n",
    "        for word in node.next.keys():\n",
    "            strs += word\n",
    "            result = self.get_str(node.next[word], strs, result)\n",
    "            strs = strs[:-1]\n",
    "        return result\n",
    "\n",
    "    def tree_huiwen(self, root):\n",
    "        result = []\n",
    "        all_str = self.get_str(root, \"\", [])\n",
    "        # if \"a\" in root.next.keys():\n",
    "        #     print(all_str)\n",
    "        for ele_str in all_str:\n",
    "            if self.huiwen(ele_str[0]):\n",
    "                result.append(ele_str[1])\n",
    "        return result\n",
    "    def huiwen(self, s):\n",
    "        if s == \"\":\n",
    "            return True\n",
    "        i = 0\n",
    "        j = len(s) - 1\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True\n",
    "            \n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.next = {}\n",
    "        self.end = None\n",
    "class QZ_tree:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "    def insert(self, s, index):\n",
    "        node = self.root\n",
    "        for i in range(len(s)):\n",
    "            if s[i] not in node.next.keys():\n",
    "                node.next[s[i]] = Node()\n",
    "            node = node.next[s[i]]\n",
    "        node.end = index\n",
    "        return\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node():\n",
    "    def __init__(self, isend=None) -> None:\n",
    "        self.e = isend\n",
    "        self.c = {}\n",
    "    def add(self, char, isend=None):\n",
    "        if char not in self.c:\n",
    "            self.c[char] = Node(isend)\n",
    "            \n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def foo(words):\n",
    "            root = Node()\n",
    "            for i in range(len(words)):\n",
    "                cur = root\n",
    "                for ch in words[i][::-1]:\n",
    "                    cur.add(ch)\n",
    "                    cur = cur.c[ch]\n",
    "                cur.e = i\n",
    "            ans = set()\n",
    "            for i in range(len(words)):\n",
    "                w, cur = words[i], root\n",
    "                for j in range(len(w) + 1):\n",
    "                    if cur.e != None:\n",
    "                        l, r, ispalindrome = j, len(w) - 1, True\n",
    "                        while l < r:\n",
    "                            if w[l] != w[r]:\n",
    "                                ispalindrome = False\n",
    "                                break\n",
    "                            l += 1\n",
    "                            r -= 1\n",
    "                        if ispalindrome and i != cur.e:\n",
    "                            ans.add((i, cur.e))\n",
    "                    if j == len(w) or w[j] not in cur.c:\n",
    "                        break\n",
    "                    cur = cur.c.get(w[j])\n",
    "            return ans\n",
    "        ans = foo(words)\n",
    "        for a, b in foo([w[::-1] for w in words]):\n",
    "            ans.add((b, a))\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.isEnd = -1\n",
    "    \n",
    "    def insert(self, w: str, i: int) -> None:\n",
    "        p = self\n",
    "        for ch in w:\n",
    "            idx = ord(ch) - ord('a')\n",
    "            if not p.children[idx]:\n",
    "                p.children[idx] = Trie()\n",
    "            p = p.children[idx]\n",
    "        p.isEnd = i\n",
    "    \n",
    "    def search(self, w: str) -> List[int]:\n",
    "        res = []\n",
    "        if self.isEnd != -1 and w == w[::-1]:\n",
    "            res.append(self.isEnd)\n",
    "        p = self\n",
    "        for j, ch in enumerate(w):\n",
    "            idx = ord(ch) - ord('a')\n",
    "            if not p.children[idx]:\n",
    "                return res\n",
    "            p = p.children[idx]\n",
    "            if p.isEnd != -1 and w[j+1:] == w[j+1:][::-1]:\n",
    "                res.append(p.isEnd)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        res = []\n",
    "        words = [(x, i) for i, x in enumerate(words)]\n",
    "        words.sort(key=lambda x: len(x[0]))\n",
    "\n",
    "        trie = Trie()\n",
    "        for w, i in words:\n",
    "            ans = trie.search(w)\n",
    "            if len(ans) > 0:\n",
    "                res += [[i, j] for j in ans]\n",
    "            trie.insert(w[::-1], i)\n",
    "\n",
    "        trie = Trie()\n",
    "        for w, i in words:\n",
    "            ans = trie.search(w[::-1])\n",
    "            if len(ans) > 0:\n",
    "                res += [[j, i] for j in ans]\n",
    "            trie.insert(w, i)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.index = -1 # represent the index of the word for this search\n",
    "        self.children = [None]*26\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    def insert(self, w, index):\n",
    "        curNode = self.root\n",
    "        for c in w:\n",
    "            cindex = ord(c)-ord('a')\n",
    "            if not curNode.children[cindex]:\n",
    "                curNode.children[cindex] = TrieNode()\n",
    "            curNode = curNode.children[cindex]\n",
    "        curNode.index = index\n",
    "    def search(self, c, node):\n",
    "        curNode = node\n",
    "        cindex = ord(c)-ord('a')\n",
    "        if not curNode or not curNode.children[cindex]:\n",
    "            return (False, None)\n",
    "        curNode = curNode.children[cindex]\n",
    "        return (curNode.index != -1, curNode)\n",
    "\n",
    "class Solution:\n",
    "    def isPalindrome(self, w, l, r):\n",
    "        # print(w, l, r)\n",
    "        if l >= r: return True\n",
    "        if w[l] != w[r]: return False\n",
    "        return self.isPalindrome(w, l+1, r-1)\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        dictTree = Trie()\n",
    "        ret = []\n",
    "        for i, w in enumerate(words):\n",
    "            dictTree.insert(w[::-1], i)\n",
    "            if w == '': dictTree.root.index = i\n",
    "        for i, w in enumerate(words):\n",
    "            curNode = dictTree.root\n",
    "            wl = len(w)\n",
    "            for j, c in enumerate(w):\n",
    "                result, curNode = dictTree.search(c, curNode)\n",
    "                # print(w, c, result)\n",
    "                if not curNode: break\n",
    "                if result and curNode.index != i and self.isPalindrome(w, j+1, wl-1):\n",
    "                    ret.append([i, curNode.index])\n",
    "            if w != '' and dictTree.root.index != -1 and self.isPalindrome(w, 0, wl-1):\n",
    "                ret.append([i, dictTree.root.index])\n",
    "                ret.append([dictTree.root.index, i])\n",
    "        dictTree = Trie()\n",
    "        for i, w in enumerate(words):\n",
    "            dictTree.insert(w, i)\n",
    "        for i, w in enumerate(words):\n",
    "            curNode = dictTree.root\n",
    "            wl = len(w)\n",
    "            for j, c in enumerate(w[::-1]):\n",
    "                # print(w, c, j)\n",
    "                result, curNode = dictTree.search(c, curNode)\n",
    "                # print(w, c, result)\n",
    "                if not curNode: break\n",
    "                if result and curNode.index != i and self.isPalindrome(w, 0, wl-j-2):\n",
    "                    if len(words[curNode.index]) != len(w):\n",
    "                        ret.append([curNode.index, i])\n",
    "        return ret \n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        m0 = {}\n",
    "        m1 = {}\n",
    "        for p, word in enumerate(words):\n",
    "            _word = '\\x01%s' % word\n",
    "            for idx in range(len(_word)):\n",
    "                if _word[idx:] == _word[idx:][::-1]:\n",
    "                    m1.setdefault(word[:idx-1], []).append(p)\n",
    "            m0[word] = p\n",
    "        l = []\n",
    "        for p, word in enumerate(words):\n",
    "            _word = word[::-1]\n",
    "            tmp = m1.get(_word, [])\n",
    "            tp = m0.get(_word)\n",
    "            if tp is not None:\n",
    "                tmp.append(tp)\n",
    "            l.extend([p0, p] for p0 in tmp if p0 != p)\n",
    "            for idx in range(len(word)):\n",
    "                if _word[idx:] == _word[idx:][::-1]:\n",
    "                    tmp = m0.get(_word[:idx])\n",
    "                    if tmp is not None:\n",
    "                        l.append([tmp, p])\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        word_idx = {}\n",
    "        backfix_word = {}\n",
    "        IdxOfPalindrome = []\n",
    "        for i in range(len(words)):\n",
    "            word = words[i]\n",
    "            word_idx[word] = i \n",
    "            if self.help(word) and word:\n",
    "                IdxOfPalindrome.append(i)\n",
    "            for j in range(len(word)-1):\n",
    "                backfix = word[len(word)-1-j:]\n",
    "                if backfix in backfix_word:\n",
    "                    backfix_word[backfix].append(word)\n",
    "                else:\n",
    "                    backfix_word[backfix] = [word]\n",
    "        #print(word_idx)\n",
    "        #print(backfix_word)\n",
    "        #print(IdxOfPalindrome)\n",
    "\n",
    "        ans = []\n",
    "        for i in range(len(words)):\n",
    "            s1 = words[i]\n",
    "            # s1不是空字符串\n",
    "            if s1:\n",
    "                # s1 == s2,s1+s2是回文~ s2==s1[::-1]\n",
    "                s2 = s1[::-1]\n",
    "                if s2 in word_idx and word_idx[s2] != i:\n",
    "                    ans.append([i,word_idx[s2]])\n",
    "                \n",
    "                # len(s1) > len(s2) ,s1 + s2是回文~ s1的前缀 == s2[::-1],且s1剩下的部分是回文\n",
    "                for j in range(len(s1)):\n",
    "                    prefix = s1[:j]\n",
    "                    \n",
    "                    if prefix[::-1] in word_idx and self.help(s1[j:]):\n",
    "                        ans.append([i,word_idx[prefix[::-1]]])\n",
    "                \n",
    "                # len(s1) < len(s2),s1 + s2是回文~ s2的后缀 == s1[::-1]，且s2剩下的部分是回文\n",
    "                if s1[::-1] in backfix_word:\n",
    "                    for s2 in backfix_word[s1[::-1]]:\n",
    "                        remain = s2[:len(s2)-len(s1)]\n",
    "                        if self.help(remain):\n",
    "                            #print(remain)\n",
    "                            ans.append([i,word_idx[s2]])\n",
    "            else:\n",
    "                for idx in IdxOfPalindrome:\n",
    "                    ans.append([i,idx])\n",
    "        return ans \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def help(self,word):\n",
    "        # 判断word是否是回文\n",
    "        if not word:\n",
    "            return True \n",
    "        n = len(word)\n",
    "        idx1,idx2 = 0,n-1\n",
    "        while idx1 < idx2:\n",
    "            if word[idx1] != word[idx2]:\n",
    "                return False\n",
    "            idx1 += 1\n",
    "            idx2 -= 1\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        words_dic = {word: i for i, word in enumerate(words)}\n",
    "        suffix_dic = collections.defaultdict(list)\n",
    "        palindromes = []\n",
    "        for word in words:\n",
    "            n = len(word)\n",
    "            if word == word[::-1] and word != \"\":\n",
    "                palindromes.append(words_dic[word])\n",
    "            for i in range(n - 1):\n",
    "                suffix = word[n - 1 - i:]\n",
    "                suffix_dic[suffix].append(word)\n",
    "        res = []\n",
    "        for i, word in enumerate(words):\n",
    "            if word:\n",
    "                # case 1: len(word1) == len(word2) -> word1 == word2[::-1]\n",
    "                if word[::-1] in words_dic and words_dic[word[::-1]] != i:\n",
    "                    res.append((i, words_dic[word[::-1]]))\n",
    "                # case 2: len(word1) < len(word2) -> word2的后缀为word1[::-1] && word2中剩余部分为palindrome\n",
    "                if word[::-1] in suffix_dic:\n",
    "                    for w in suffix_dic[word[::-1]]:\n",
    "                        remain = w[:-len(word)]\n",
    "                        if remain == remain[::-1]:\n",
    "                            res.append((i, words_dic[w]))\n",
    "                # case 3: len(word1) > len(word2) -> word1的前缀为word2[::-1] && word1中剩余部分为palindrome\n",
    "                for j in range(-1, len(word) - 1):\n",
    "                    prefix = word[:j + 1]\n",
    "                    if prefix[::-1] in words_dic and word[j + 1:] == word[j + 1:][::-1]:\n",
    "                        res.append((i, words_dic[prefix[::-1]]))\n",
    "            else:  # 所有palindrome都可以\n",
    "                for idx in palindromes:\n",
    "                    res.append((i, idx))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        word_idx = {word: i for i, word in enumerate(words)}\n",
    "        words = set(words)\n",
    "        suffix_words = collections.defaultdict(list)  # suffix: [word]\n",
    "        for word in words:\n",
    "            for i in range(len(word), -1, -1):\n",
    "                suffix = word[i:]\n",
    "                suffix_words[suffix].append(word)\n",
    "        # find palindrome pairs\n",
    "        res = []\n",
    "        for word, i in word_idx.items():\n",
    "            # case 1: len(word1) == len(word2) and word1 == word2[::-1] and word1 != word2\n",
    "            if word[::-1] in words and word[::-1] != word:\n",
    "                res.append([i, word_idx[word[::-1]]])\n",
    "            # case 2: len(word1) < len(word2) =>\n",
    "            # word1 == word2[-len(word1):][::-1] + word2[:len(word2) - len(word1)] is palindrome\n",
    "            for w in suffix_words[word[::-1]]:\n",
    "                if len(w) > len(word) and w[:len(w) - len(word)] == w[:len(w) - len(word)][::-1]:\n",
    "                    res.append([i, word_idx[w]])\n",
    "            # case 3: len(word1) > len(word2) =>\n",
    "            # word1 == word2[::-1] + word2[:len(word2) - len(word1)] is palindrome\n",
    "            for j in range(len(word)):\n",
    "                if word[:j][::-1] in words and word[j:] == word[j:][::-1]:\n",
    "                    res.append([i, word_idx[word[:j][::-1]]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.childs = defaultdict(Trie)\n",
    "        self.indexs = []\n",
    "\n",
    "    def add(self, word, value):\n",
    "        cur = self\n",
    "        for w in word:\n",
    "            cur = cur.childs[w]\n",
    "        cur.indexs.append(value)\n",
    "\n",
    "    def get(self, w):\n",
    "        if w not in self.childs:\n",
    "            return None\n",
    "        return self.childs[w]\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def get_ans(words):\n",
    "            trie = Trie()\n",
    "            ans = []\n",
    "            def isPalindrome(s):\n",
    "                l = 0\n",
    "                r = len(s) - 1\n",
    "                while l < r:\n",
    "                    if s[l] != s[r]:\n",
    "                        return False\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                return True\n",
    "\n",
    "            for j, word in enumerate(words):\n",
    "                n = len(word)\n",
    "                if trie.indexs:\n",
    "                    if isPalindrome(word):\n",
    "                        for i in trie.indexs:\n",
    "                            ans.append([i, j])\n",
    "                cur = trie\n",
    "                for k in range(n-1,-1,-1):\n",
    "                    cur = cur.get(word[k])\n",
    "                    if cur is None:\n",
    "                        break\n",
    "                    #print(word, j, k, cur.indexs)\n",
    "                    for i in cur.indexs:\n",
    "                        if isPalindrome(words[i] + word):\n",
    "                            ans.append([i, j])\n",
    "                if cur:\n",
    "                    q = deque(cur.childs.values())\n",
    "                    while q:\n",
    "                        cur = q.popleft()\n",
    "                        for i in cur.indexs:\n",
    "                            if isPalindrome(words[i] + word):\n",
    "                                ans.append([i, j])\n",
    "\n",
    "                        for nxt in cur.childs.values():\n",
    "                            q.append(nxt)\n",
    "                trie.add(word, j)\n",
    "            return ans\n",
    "        a = get_ans(words)\n",
    "        b = get_ans(words[::-1])\n",
    "        n = len(words) - 1\n",
    "        # print(b, n)\n",
    "        b = [[n - x, n - y] for x, y in b]\n",
    "        return  a + b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "前缀树\n",
    "'''\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = dict()\n",
    "        return  \n",
    "\n",
    "    def insert(self, s, i):\n",
    "        cur = self.root\n",
    "        for x in s:\n",
    "            if x not in cur:\n",
    "                cur[x] = dict()\n",
    "            cur = cur[x]\n",
    "        #if \"#\" in cur:\n",
    "        #    print(cur[\"#\"], i)\n",
    "        #    print(\"hahahaaha\")    \n",
    "        cur[\"#\"] = i\n",
    "\n",
    "    \n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        isEmpty = words.index(\"\") if \"\" in words else -1\n",
    "        ans = []\n",
    "        n = len(words)\n",
    "        pre = Trie()\n",
    "        last = Trie()\n",
    "        #1.\n",
    "        for i, w in enumerate(words):\n",
    "\n",
    "            cur = pre.root\n",
    "            if isEmpty != -1 and w and w == w[::-1]:\n",
    "                ans.append([isEmpty, i])\n",
    "                ans.append([i, isEmpty])\n",
    "\n",
    "            for j in range(len(w)-1, -1, -1): \n",
    "                if w[j] in cur:\n",
    "                    cur = cur[w[j]]\n",
    "                    if \"#\" in cur and w[:j] == w[:j][::-1]:\n",
    "                        ans.append([cur[\"#\"], i])\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            cur = last.root\n",
    "            for j in range(len(w)):\n",
    "                if w[j] in cur:\n",
    "                    cur = cur[w[j]]\n",
    "                    if \"#\" in cur and w[j+1:] == w[j+1:][::-1]:\n",
    "                        ans.append([i, cur[\"#\"]])\n",
    "                else:\n",
    "                    break        \n",
    "\n",
    "            last.insert(w[::-1], i)\n",
    "            pre.insert(w, i)\n",
    "\n",
    "\n",
    "        pre = Trie()\n",
    "        last = Trie()\n",
    "        #print(pre.root, last.root)\n",
    "        #2.\n",
    "        for i in range(n-1, -1, -1):\n",
    "            w = words[i]\n",
    "\n",
    "            cur = pre.root\n",
    "            for j in range(len(w)-1, 0, -1):\n",
    "                if w[j] in cur:\n",
    "                    cur = cur[w[j]]\n",
    "                    if \"#\" in cur and w[:j] == w[:j][::-1]:\n",
    "                        ans.append([cur[\"#\"], i])\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            cur = last.root\n",
    "            for j in range(len(w)-1):\n",
    "                if w[j] in cur:\n",
    "                    cur = cur[w[j]]\n",
    "                    if \"#\" in cur and w[j+1:] == w[j+1:][::-1]:\n",
    "                        ans.append([i, cur[\"#\"]])\n",
    "                else:\n",
    "                    break        \n",
    "\n",
    "            last.insert(w[::-1], i)\n",
    "            pre.insert(w, i)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.dct = dict()\n",
    "\n",
    "    def add(self, word, i):\n",
    "        cur = self.dct\n",
    "        for va in word:\n",
    "            if va not in cur:\n",
    "                cur[va] = dict()\n",
    "            cur = cur[va]\n",
    "        cur['isEnd'] = i\n",
    "        return\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words):\n",
    "        \n",
    "        # 按照长度进行排序\n",
    "        n = len(words)\n",
    "        for i in range(n):\n",
    "            words[i] = [words[i], i]\n",
    "        words.sort(key=lambda x: [len(x[0]), x[0]])\n",
    "        \n",
    "        # 正反字典树\n",
    "        trie = Trie()\n",
    "        trie_rev = Trie()\n",
    "\n",
    "        def check(l, r):\n",
    "            while l < r:\n",
    "                if word[r] == word[l]:\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    break\n",
    "            return l >= r\n",
    "\n",
    "        res = []\n",
    "        for word, i in words:\n",
    "            m = len(word)\n",
    "            # 当前字符在后面\n",
    "            cur = trie.dct\n",
    "            j = m-1\n",
    "            search = True\n",
    "            while j >= 0:\n",
    "                if 'isEnd' in cur and check(0, j):\n",
    "                    res.append([cur['isEnd'], i])\n",
    "                if word[j] in cur:\n",
    "                    cur = cur[word[j]]\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    search = False\n",
    "                    break\n",
    "            if search and 'isEnd' in cur and check(0, j):\n",
    "                res.append([cur['isEnd'], i])\n",
    "            trie.add(word, i)\n",
    "\n",
    "            # 当前字符在前面\n",
    "            cur = trie_rev.dct\n",
    "            j = 0\n",
    "            search = True\n",
    "            while j <= m-1:\n",
    "                if 'isEnd' in cur and check(j, m-1):\n",
    "                    res.append([i, cur['isEnd']])\n",
    "                if word[j] in cur:\n",
    "                    cur = cur[word[j]]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    search = False\n",
    "                    break\n",
    "            if search and 'isEnd' in cur and check(j, m-1):\n",
    "                res.append([i, cur['isEnd']])\n",
    "            trie_rev.add(word[::-1], i)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 10 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "\n",
    "        base = len(set(''.join(words))) + 1\n",
    "\n",
    "        @cache\n",
    "        def getNumFromS(i):\n",
    "            if not i: return 0\n",
    "            return ord(i) - ord('a') + 1\n",
    "\n",
    "        @cache\n",
    "        def getHandleArr(s):\n",
    "            if not s: return [0]\n",
    "            res = []\n",
    "            seq = 0\n",
    "            for i in s:\n",
    "                n = getNumFromS(i)\n",
    "                seq = (seq * base + n) % MOD\n",
    "                res.append(seq)\n",
    "            return res\n",
    "\n",
    "        @cache\n",
    "        def handle(s: str):\n",
    "            if not s: return []\n",
    "            seq = rev = 0\n",
    "            mi = 1\n",
    "            res = []\n",
    "            for index, i in enumerate(s):\n",
    "                n = getNumFromS(i)\n",
    "                rev = (n * mi + rev) % MOD\n",
    "                seq = (seq * base + n) % MOD\n",
    "                mi *= base\n",
    "                if seq == rev: res.append(index)\n",
    "\n",
    "            if not res: return [0]\n",
    "            rev = getHandleArr(reversed(s))\n",
    "            rev.reverse()\n",
    "            res = [rev[i + 1] if i + 1 < len(s) else 0 for i in res]\n",
    "            res.append(rev[0])\n",
    "            return res\n",
    "\n",
    "\n",
    "        def getAns(words: List[str], r = False):\n",
    "            res = set()\n",
    "            m = defaultdict(list)\n",
    "            for index, i in enumerate(words):\n",
    "                m[getHandleArr(i)[-1]].append(index)\n",
    "            \n",
    "            for index, i in enumerate(words):\n",
    "                for key in handle(i):\n",
    "                    for preIndex in m[key]:\n",
    "                        if index == preIndex: continue\n",
    "                        if r:\n",
    "                            res.add((index, preIndex))\n",
    "                        else:\n",
    "                            res.add((preIndex, index))\n",
    "            return res\n",
    "\n",
    "\n",
    "        res1 = getAns(words)\n",
    "        res2 = getAns([''.join(list(reversed(i))) for i in words], True)\n",
    "        res1.update(res2)\n",
    "\n",
    "        del getNumFromS\n",
    "        del getHandleArr\n",
    "        del handle\n",
    "\n",
    "        return list(res1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #方法1：字典树+dfs, 2500ms\n",
    "    '''\n",
    "    思路： 如： abcc和ba\n",
    "    abcc +ba 两个字符串进行匹配，采用字典树将所有字符串逆序加入(也就是加入时表现为：ccba、ab)。\n",
    "    然后枚举每个字符串，匹配字典树然后发现 字符串abcc 和字典树存的逆序ab是匹配的，\n",
    "    那就只需要判断后面未匹配的字符串(cc)是否为回文串，答案是。所以abcc+ba是回文串。\n",
    "    但是你会发现出现这种串 ab+ccba，怎么判断？枚举到ab的时候还没到逆序abcc的终点，不好判断。\n",
    "    那我就将全部字符串翻转 重复下上面的操作，即变为 abcc和ba串进行匹配。\n",
    "\n",
    "    总结：对words进行正序和逆序两个匹配，然后结果相加。 注意：\n",
    "\n",
    "    正序匹配的是 串1.size>=串2.size\n",
    "    逆序匹配的是 串1.size<串2.size\n",
    "    '''\n",
    "\n",
    "    def palindromePairs(self, words):\n",
    "        import collections\n",
    "        from functools import reduce\n",
    "        \n",
    "        Trie = lambda: collections.defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "        for i, word in enumerate(words):\n",
    "            reduce(dict.__getitem__, word, trie)[\"END\"] = i\n",
    "        def isPalindrome(s, p):\n",
    "            left, right = p, len(s) - 1 - p\n",
    "            return left >= right or s[left] == s[right] and isPalindrome(s, p + 1)\n",
    "        def dfs(curr, word, j):\n",
    "            if \"END\" in curr and curr[\"END\"] != i:\n",
    "                if isPalindrome(words[curr[\"END\"]] + word, len(word) - 1 - j):\n",
    "                    res.append([curr[\"END\"], i])\n",
    "            if j == -1:\n",
    "                for node in curr:\n",
    "                    if node != \"END\":\n",
    "                        dfs(curr[node], word, j)\n",
    "            else: dfs(curr[word[j]], word, j - 1) \n",
    "        res = []\n",
    "        for i, word in enumerate(words):\n",
    "            dfs(trie, word, len(word) - 1)\n",
    "        return res\n",
    "\n",
    "    '''\n",
    "    #方法2：1900ms\n",
    "    def palindromePairs(self, words):\n",
    "        ans = []\n",
    "        wordDict = {word:i for i,word in enumerate(words)}\n",
    "        for j in range(len(words)):\n",
    "            if words[j] == words[j][::-1] and words[j] != \"\" and \"\" in wordDict:\n",
    "                ans.append([j, wordDict.get(\"\")])\n",
    "                ans.append([wordDict.get(\"\"), j])\n",
    "            if words[j] != words[j][::-1] and words[j][::-1] in wordDict and len(words[j]) > 1:\n",
    "                ans.append([wordDict.get(words[j][::-1]), j])\n",
    "            for i in range(1, len(words[j])):\n",
    "                pre = words[j][:i]\n",
    "                post = words[j][i:]\n",
    "                rPre = pre[::-1]\n",
    "                rPost = post[::-1]\n",
    "                if post == rPost and rPre in wordDict:\n",
    "                    ans.append([j,wordDict.get(rPre)])\n",
    "                if pre == rPre and rPost in wordDict:\n",
    "                    ans.append([wordDict.get(rPost),j])\n",
    "        return ans\n",
    "\n",
    "    #方法3: 2200ms\n",
    "    def palindromePairs(self, words):\n",
    "        valid_pals = []\n",
    "        wordsDict = {word: i for i, word in enumerate(words)}\n",
    "        for word, k in wordsDict.items():\n",
    "            n = len(word)\n",
    "            for j in range(n + 1):\n",
    "                pre = word[:j]\n",
    "                post = word[j:]\n",
    "                # 比如\"ccab\",pre=\"cc\",post=\"ab\",rPost=\"ba\",\"baccab\"是回文\n",
    "                if pre == pre[::-1]:\n",
    "                    rPost = post[::-1]\n",
    "                    if rPost != word and rPost in wordsDict:\n",
    "                        valid_pals.append([wordsDict[rPost], k])\n",
    "                # 比如\"abcc\",pre=\"ab\",post=\"cc\",rPre=\"ba\",\"abccba\"是回文\n",
    "                if j != n and post == post[::-1]:\n",
    "                    rPre = pre[::-1]\n",
    "                    if rPre != word and rPre in wordsDict:\n",
    "                        valid_pals.append([k, wordsDict[rPre]])\n",
    "        return valid_pals\n",
    "    '''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #方法1：字典树+dfs, 2500ms\n",
    "    '''\n",
    "    思路： 如： abcc和ba\n",
    "    abcc +ba 两个字符串进行匹配，采用字典树将所有字符串逆序加入(也就是加入时表现为：ccba、ab)。\n",
    "    然后枚举每个字符串，匹配字典树然后发现 字符串abcc 和字典树存的逆序ab是匹配的，\n",
    "    那就只需要判断后面未匹配的字符串(cc)是否为回文串，答案是。所以abcc+ba是回文串。\n",
    "    但是你会发现出现这种串 ab+ccba，怎么判断？枚举到ab的时候还没到逆序abcc的终点，不好判断。\n",
    "    那我就将全部字符串翻转 重复下上面的操作，即变为 abcc和ba串进行匹配。\n",
    "\n",
    "    总结：对words进行正序和逆序两个匹配，然后结果相加。 注意：\n",
    "\n",
    "    正序匹配的是 串1.size>=串2.size\n",
    "    逆序匹配的是 串1.size<串2.size\n",
    "    '''\n",
    "\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        Trie = lambda: collections.defaultdict(Trie)\n",
    "        trie = Trie()\n",
    "        for i, word in enumerate(words):\n",
    "            reduce(dict.__getitem__, word, trie)[\"END\"] = i\n",
    "        def isPalindrome(s, p):\n",
    "            left, right = p, len(s) - 1 - p\n",
    "            return left >= right or s[left] == s[right] and isPalindrome(s, p + 1)\n",
    "        def dfs(curr, word, j):\n",
    "            if \"END\" in curr and curr[\"END\"] != i:\n",
    "                if isPalindrome(words[curr[\"END\"]] + word, len(word) - 1 - j):\n",
    "                    res.append([curr[\"END\"], i])\n",
    "            if j == -1:\n",
    "                for node in curr:\n",
    "                    if node != \"END\":\n",
    "                        dfs(curr[node], word, j)\n",
    "            else: dfs(curr[word[j]], word, j - 1) \n",
    "        res = []\n",
    "        for i, word in enumerate(words):\n",
    "            dfs(trie, word, len(word) - 1)\n",
    "        return res\n",
    "\n",
    "    '''\n",
    "    #方法2：1900ms\n",
    "    def palindromePairs(self, words):\n",
    "        ans = []\n",
    "        dataset = {word:i for i,word in enumerate(words)}\n",
    "        for j in range(len(words)):\n",
    "            if words[j] == words[j][::-1] and words[j] != \"\" and \"\" in dataset:\n",
    "                ans.append([j, dataset.get(\"\")])\n",
    "                ans.append([dataset.get(\"\"), j])\n",
    "            if words[j] != words[j][::-1] and words[j][::-1] in dataset and len(words[j]) > 1:\n",
    "                ans.append([dataset.get(words[j][::-1]), j])\n",
    "            for i in range(1, len(words[j])):\n",
    "                pre = words[j][:i]\n",
    "                post = words[j][i:]\n",
    "                rPre = pre[::-1]\n",
    "                rPost = post[::-1]\n",
    "                if post == rPost and rPre in dataset:\n",
    "                    ans.append([j,dataset.get(rPre)])\n",
    "                if pre == rPre and rPost in dataset:\n",
    "                    ans.append([dataset.get(rPost),j])\n",
    "        return ans\n",
    "\n",
    "    #方法3: 2200ms\n",
    "    def palindromePairs(self, words):\n",
    "        valid_pals = []\n",
    "        wordsDict = {word: i for i, word in enumerate(words)}\n",
    "        for word, k in wordsDict.items():\n",
    "            n = len(word)\n",
    "            for j in range(n + 1):\n",
    "                pre = word[:j]\n",
    "                post = word[j:]\n",
    "                # 比如\"ccab\",pre=\"cc\",post=\"ab\",rPost=\"ba\",\"baccab\"是回文\n",
    "                if pre == pre[::-1]:\n",
    "                    rPost = post[::-1]\n",
    "                    if rPost != word and rPost in wordsDict:\n",
    "                        valid_pals.append([wordsDict[rPost], k])\n",
    "                # 比如\"abcc\",pre=\"ab\",post=\"cc\",rPre=\"ba\",\"abccba\"是回文\n",
    "                if j != n and post == post[::-1]:\n",
    "                    rPre = pre[::-1]\n",
    "                    if rPre != word and rPre in wordsDict:\n",
    "                        valid_pals.append([k, wordsDict[rPre]])\n",
    "        return valid_pals\n",
    "    '''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class TireTree():\n",
    "    def __init__(self):\n",
    "        self.children = [None] * (26)\n",
    "        self.palindrome = [] # 后面是回文的\n",
    "        self.word = -1   # 这个单词是啥\n",
    "        self.is_end = False\n",
    "    def insert(self, word, j):\n",
    "        root = self\n",
    "        for i,ch in enumerate(word):\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            if not root.children[idx]:\n",
    "                root.children[idx] = TireTree()\n",
    "            root = root.children[idx]\n",
    "            if i+1 < len(word) and word[i+1:] == word[i+1:][::-1]:\n",
    "                root.palindrome.append( j )\n",
    "        root.word = j\n",
    "        root.is_end = True\n",
    "\n",
    "    def query(self, word, j, res):\n",
    "        root = self\n",
    "        for i, ch in enumerate(word):\n",
    "            idx = ord(ch) - ord(\"a\")\n",
    "            if not root.children[idx]:\n",
    "                if root.is_end and word[i:] == word[i:][::-1]:\n",
    "                    res.append( [root.word, j]  )\n",
    "                return res\n",
    "            if root.is_end:\n",
    "                if word[i:] == word[i:][::-1]:\n",
    "                    res.append( [root.word, j]  )\n",
    "\n",
    "            root = root.children[idx]\n",
    "\n",
    "        if root.is_end:\n",
    "            res.append( [root.word, j]  )\n",
    "        for p in root.palindrome:\n",
    "            res.append( (p, j) )\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "\n",
    "        t = TireTree()\n",
    "        for i,word in enumerate(words):\n",
    "            t.insert(word, i)\n",
    "\n",
    "        res = []\n",
    "        for i, word in enumerate(words):\n",
    "            res = t.query(word[::-1], i, res)\n",
    "            # print(word, res, i )\n",
    "        ans = []\n",
    "        for i,j in res:\n",
    "            if i != j:\n",
    "                ans.append([i,j])\n",
    "\n",
    "        for i, word in enumerate(words):\n",
    "            if word == \"\":\n",
    "                for j in range(len(words)):\n",
    "                    if i != j and words[j] == words[j][::-1]:\n",
    "                        ans.append([j, i])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.palindrome_suffixes = []\n",
    "        self.children = [None] * 26\n",
    "        self.word_id = -1\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def insert(root, word, word_id):\n",
    "            for i in range(len(word) - 1, -1, -1):\n",
    "                c = ord(word[i]) - ord('a')\n",
    "                if not root.children[c]:\n",
    "                    root.children[c] = TrieNode()\n",
    "                if is_palindrome(word, 0, i):\n",
    "                    root.palindrome_suffixes.append(word_id)\n",
    "                root = root.children[c]\n",
    "            root.word_id = word_id\n",
    "            root.palindrome_suffixes.append(word_id)\n",
    "\n",
    "        def search(root, word, word_id, result):\n",
    "            for i, c in enumerate(word):\n",
    "                if root.word_id >= 0 and root.word_id != word_id and is_palindrome(word, i, len(word) - 1):\n",
    "                    result.append([word_id, root.word_id])\n",
    "                root = root.children[ord(c) - ord('a')]\n",
    "                if not root:\n",
    "                    return\n",
    "            for j in root.palindrome_suffixes:\n",
    "                if j != word_id:\n",
    "                    result.append([word_id, j])\n",
    "\n",
    "        def is_palindrome(word, left, right):\n",
    "            while left < right:\n",
    "                if word[left] != word[right]:\n",
    "                    return False\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            return True\n",
    "\n",
    "        root = TrieNode()\n",
    "        for i, word in enumerate(words):\n",
    "            insert(root, word, i)\n",
    "\n",
    "        result = []\n",
    "        for i, word in enumerate(words):\n",
    "            search(root, word, i, result)\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def get_boundarys(input_str):\n",
    "    n = len(input_str)\n",
    "    boundary_list = [0] * n\n",
    "    ref_idx = 0\n",
    "    ref_boundary = 0\n",
    "    for i in range(1, n):\n",
    "        j = 2 * ref_idx - i\n",
    "        if j < 0:\n",
    "            end = min(2 * i, n - 1)\n",
    "            for j in range(i+1, end + 1):\n",
    "                if input_str[2 * i - j] != input_str[j]:\n",
    "                    boundary_list[i] = j - i - 1\n",
    "                    break\n",
    "            else:\n",
    "                boundary_list[i] = end - i\n",
    "            ref_idx = i\n",
    "            ref_boundary = boundary_list[i]\n",
    "        else:\n",
    "            if j - boundary_list[j] > ref_idx - ref_boundary:\n",
    "                boundary_list[i] = boundary_list[j]\n",
    "            else:\n",
    "                end = min(2 * i, n - 1)\n",
    "                for j in range(ref_idx + ref_boundary + 1, end + 1):\n",
    "                    if input_str[2 * i - j] != input_str[j]:\n",
    "                        boundary_list[i] = j - i - 1\n",
    "                        break\n",
    "                else:\n",
    "                    boundary_list[i] = end - i\n",
    "                if i + boundary_list[i] >= ref_idx + ref_boundary:\n",
    "                    ref_idx = i\n",
    "                    ref_boundary = boundary_list[i]\n",
    "    return boundary_list\n",
    "\n",
    "def get_match_symbols(input_str):\n",
    "    if not input_str:\n",
    "        return [], []\n",
    "    boundary_list = get_boundarys('#{}#'.format('#'.join(input_str)))\n",
    "    n = len(input_str)\n",
    "    head_match_symbols = [False] * n\n",
    "    tail_match_symbols = [False] * n\n",
    "    head_idx = 1\n",
    "    tail_idx = 2 * n - 1\n",
    "    for i, boundary in enumerate(boundary_list):\n",
    "        left, right = i - boundary, i + boundary\n",
    "        if left <= head_idx <= right:\n",
    "            head_match_symbols[right//2-1] = True\n",
    "        if  left <= tail_idx <= right:\n",
    "            tail_match_symbols[left // 2] = True\n",
    "    return head_match_symbols, tail_match_symbols\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.indexs = []\n",
    "        self.word_idx = None\n",
    "        self.children = collections.defaultdict(Node)\n",
    "\n",
    "    def insert(self, word, tail_match_symbols, idx):\n",
    "        n = len(word)\n",
    "        cur_node = self\n",
    "        if not n:\n",
    "            cur_node.word_idx = idx\n",
    "            return\n",
    "        if tail_match_symbols[0]:\n",
    "            cur_node.indexs.append(idx)\n",
    "        for i, char in enumerate(word):\n",
    "            cur_node = cur_node.children[char]\n",
    "            if i < n - 1 and tail_match_symbols[i+1]:\n",
    "                cur_node.indexs.append(idx)\n",
    "        cur_node.word_idx = idx\n",
    "    \n",
    "    def match(self, word, head_match_symbols, idx):\n",
    "        ret = []\n",
    "        n = len(word)\n",
    "        cur_node = self\n",
    "        if not n:\n",
    "            for j in cur_node.indexs:\n",
    "                ret.append([j, idx])\n",
    "            return ret\n",
    "        if cur_node.word_idx is not None:\n",
    "            if head_match_symbols[-1]:\n",
    "                ret.append([cur_node.word_idx, idx])\n",
    "        for i in range(n-1, -1, -1):\n",
    "            char = word[i]\n",
    "            if char in cur_node.children:\n",
    "                cur_node = cur_node.children[char]\n",
    "                if cur_node.word_idx is not None and cur_node.word_idx != idx:\n",
    "                    if i and head_match_symbols[i-1]:\n",
    "                        ret.append([cur_node.word_idx, idx])\n",
    "            else:\n",
    "                break\n",
    "        else:\n",
    "            for j in cur_node.indexs:\n",
    "                if j != idx:\n",
    "                    ret.append([j, idx])\n",
    "            if cur_node.word_idx is not None and cur_node.word_idx != idx:\n",
    "                ret.append([cur_node.word_idx, idx])\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        match_symbols_dict = dict()\n",
    "        for word in words:\n",
    "            match_symbols_dict[word] =  get_match_symbols(word)\n",
    "        root = Node()\n",
    "        for i, word in enumerate(words):\n",
    "            tail_match_symbols = match_symbols_dict[word][1]\n",
    "            root.insert(word, tail_match_symbols, i)\n",
    "        ret = []\n",
    "        for i, word in enumerate(words):\n",
    "            head_match_symbols = match_symbols_dict[word][0]\n",
    "            res = root.match(word, head_match_symbols, i)\n",
    "            if res:\n",
    "                ret.extend(res)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children={}\n",
    "        self.end=[]\n",
    "        self.pa=[]\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        #第一步，对每个单词从后向前的顺序建树，判断是否是终点或者是回文串，时间复杂度O(NM)\n",
    "        #第二步，对字符串预处理，判断每个字符串需要的最少后缀是什么\n",
    "        root=Trie()\n",
    "        min_suf=[]\n",
    "        ispa=[]\n",
    "        blank=[]\n",
    "        for j,word in enumerate(words):\n",
    "            f=False\n",
    "            if not word:\n",
    "                blank.append(j)\n",
    "                min_suf.append('')\n",
    "                continue\n",
    "            \n",
    "            if word==word[::-1]:\n",
    "                ispa.append(j)\n",
    "\n",
    "                f=True\n",
    "                min_suf.append('')\n",
    "            temp=''\n",
    "            node=root\n",
    "            for i in range(len(word)-1,-1,-1):\n",
    "                if word[i] not in node.children:\n",
    "                    node.children[word[i]]=Trie()\n",
    "                node=node.children[word[i]]\n",
    "                if i!=0 and word[:i]==word[:i][::-1]:\n",
    "                    node.pa.append(j)\n",
    "                temp=word[len(word)-i-1]+temp\n",
    "\n",
    "                \n",
    "                \n",
    "                if not f and word+temp==(word+temp)[::-1]:\n",
    "                    f=True\n",
    "                    min_suf.append(temp)\n",
    "            node.end.append(j)\n",
    "\n",
    "\n",
    "\n",
    "        #第三步，先计算非空字符串组成的回文串\n",
    "        res=[]\n",
    "        for i,word in enumerate(words):\n",
    "            if word:\n",
    "                node=root\n",
    "                for j,c in enumerate(word):\n",
    "                    if c not in node.children:\n",
    "                        break\n",
    "                    node=node.children[c]\n",
    "                    if j>=len(min_suf[i])-1:\n",
    "                        for k in node.end:\n",
    "                            if k!=i and words[i]+words[k]==(words[i]+words[k])[::-1]:\n",
    "                                res.append([i,k])\n",
    "                    if j==len(word)-1:\n",
    "                        for k in node.pa:\n",
    "                            if k!=i:\n",
    "                                res.append([i,k])\n",
    "\n",
    "\n",
    "        #第四步，计算回文串和空字符\n",
    "        for i in ispa:\n",
    "            for j in blank:\n",
    "                res.append([i,j])\n",
    "                res.append([j,i])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    __slots__ = 'chi', 'val'\n",
    "    def __init__(self, val=None):\n",
    "        self.chi = {}\n",
    "        self.val = val\n",
    "    def __repr__(self):\n",
    "        if self.val is None:\n",
    "            return f\"TrieNode(nchi:{len(self.chi)})\"\n",
    "        return f\"TrieNode(val:{repr(self.val)} nchi:{len(self.chi)})\"\n",
    "\n",
    "class Trie:\n",
    "    \"\"\" implement as a `defaultdict`, \n",
    "    theoretical data structure, cost too much memory\n",
    "    key is `str` (allow empty), value can't store `None` \"\"\"\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "    \n",
    "    def __setitem__(self, key, val):\n",
    "        cur = self._set(key)\n",
    "        cur.val = val\n",
    "    def setdefault(self, key, default):\n",
    "        cur = self._set(key)\n",
    "        if cur.val is None:  \n",
    "            cur.val = default\n",
    "        return cur.val\n",
    "    def _set(self, key):\n",
    "        \"\"\" create new TrieNode by key and return the node key locate\"\"\"\n",
    "        cur = self.root\n",
    "        for c in key:\n",
    "            if c not in cur.chi: cur.chi[c] = TrieNode()\n",
    "            cur = cur.chi[c]\n",
    "        return cur\n",
    "    def _get(self, key):\n",
    "        \"\"\" get TrieNode by key if not found return None \"\"\"\n",
    "        cur = self.root\n",
    "        for c in key:\n",
    "            if c not in cur.chi: return None\n",
    "            cur = cur.chi[c]\n",
    "        return cur\n",
    "    \n",
    "    def get(self, key, default=None):\n",
    "        \"\"\" get TrieNode that has val by key, if not found return `default`\"\"\"\n",
    "        node = self._get(key)\n",
    "        if node is None or node.val is None: return default\n",
    "        return node.val\n",
    "    \n",
    "    def keys(self):\n",
    "        \"\"\" if prefix is empty, it iterate the whole tree \"\"\"\n",
    "        path = []\n",
    "        for node in self._traverse(self.root, path):\n",
    "            if node.val!=None: yield \"\".join(path)\n",
    "    \n",
    "    def items(self):\n",
    "        path = []\n",
    "        for node in self._traverse(self.root,  path):\n",
    "            if node.val!=None: yield \"\".join(path), node.val\n",
    "\n",
    "    def num_nodes(self, valid=False):\n",
    "        ret = 0\n",
    "        if valid:\n",
    "            for node in self._traverse(self.root):\n",
    "                if node.val!=None: ret += 1\n",
    "        else:\n",
    "            for node in self._traverse(self.root): ret += 1\n",
    "        return ret\n",
    "\n",
    "    def _traverse(self, root, path=[]):\n",
    "        \"\"\" iterate node of subtree at `root` in preorder \"\"\"\n",
    "        def dfs(x):\n",
    "            yield x\n",
    "            for k,v in x.chi.items():\n",
    "                path.append(k)\n",
    "                yield from dfs(v)\n",
    "                path.pop()\n",
    "        yield from dfs(root)\n",
    "    def pop(self, key, default=None):\n",
    "        cur = self.root\n",
    "        nodes = deque([(None,cur)]) # from childs to parent\n",
    "        for c in key:\n",
    "            if c not in cur.chi: return default\n",
    "            cur = cur.chi[c]\n",
    "            nodes.appendleft((c, cur))\n",
    "        \n",
    "        ch_tochi, chi = nodes.popleft()\n",
    "        if chi.val is None : return default\n",
    "        ret = chi.val; chi.val = None\n",
    "        if len(chi.chi)!=0: return ret\n",
    "        while nodes:\n",
    "            # loop inv: len(chi.chi) == 0 and None==chi.val\n",
    "            ch_topar, par = nodes.popleft()\n",
    "            del par.chi[ch_tochi]\n",
    "            if len(par.chi)>=1 or par.val!=None: return ret\n",
    "            ch_tochi, chi = ch_topar, par\n",
    "        # in this case, chi == self.root\n",
    "        return ret\n",
    "    def __delitem__(self, key):\n",
    "        ret = self.pop(key)\n",
    "        if ret is None: raise KeyError(f\"{key}\")\n",
    "\n",
    "    def __getitem__(self, key):\n",
    "        ret = self.get(key)\n",
    "        if ret is None: raise KeyError(f\"{key}\")\n",
    "        return ret\n",
    "    def __iter__(self): yield from self.keys()\n",
    "    def __repr__(self):\n",
    "        \"\"\" repr as a dictionary\"\"\"\n",
    "        inner = \", \".join( f'{repr(k)}:{v}' for k,v in self.items )\n",
    "        return f\"Trie{{{inner}}}\"\n",
    "    \n",
    "    def pprint(self, file=None):\n",
    "        \"\"\" expand like file tree structure\"\"\"\n",
    "        lines = deque()\n",
    "        d = 0\n",
    "        mem = 0\n",
    "        def preorder(x):\n",
    "            nonlocal d,mem\n",
    "            mem += sys.getsizeof(x) + sys.getsizeof(x.chi)\n",
    "            for k,v in x.chi.items():\n",
    "                yield k,v.val\n",
    "                d+=1\n",
    "                yield from preorder(v)\n",
    "                d-=1\n",
    "        for key, val in preorder(self.root):\n",
    "            if val is None:\n",
    "                line = '    '*d + key\n",
    "            else:\n",
    "                line = '    '*d + key + f\"({val})\"\n",
    "            lines.append(line)\n",
    "        \n",
    "        lines.appendleft(f\"Trie{{n_node:{1+len(lines)}, mem: {mem/1000:.1f}KB }}:\")\n",
    "        if file is None:\n",
    "            for line in lines:\n",
    "                print(line)\n",
    "        else:\n",
    "            with open(file, 'w') as f:\n",
    "                f.write(\"\\n\".join(lines))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        prefix,suffix,word2idx = Trie(),Trie(),{}\n",
    "        for i,word in enumerate(words):\n",
    "            prefix[word] = i\n",
    "            suffix[reversed(word)] = i\n",
    "            word2idx[word] = i\n",
    "        \n",
    "        for i,word in enumerate(words):\n",
    "            node = prefix.root\n",
    "            for c in reversed(word):\n",
    "                if node.val!=None:\n",
    "                    j = node.val\n",
    "                    concat_word = words[j]+word\n",
    "                    if i!=j and concat_word==concat_word[::-1]:\n",
    "                        ans.append([j,i])\n",
    "                if c not in node.chi:  break\n",
    "                node = node.chi[c]\n",
    "\n",
    "            node = suffix.root\n",
    "            for c in word:\n",
    "                if node.val!=None:\n",
    "                    j = node.val\n",
    "                    concat_word = word+words[j]\n",
    "                    if i!=j and concat_word==concat_word[::-1]:\n",
    "                        ans.append([i,j])\n",
    "                if c not in node.chi: break\n",
    "                node = node.chi[c]\n",
    "\n",
    "            revword = word[::-1]\n",
    "            if revword in word2idx:\n",
    "                j = word2idx[revword]\n",
    "                if i!=j:\n",
    "                    ans.append([i,j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.childs = defaultdict(Trie)\n",
    "        self.indexs = []\n",
    "        self.pIndexs = []\n",
    "    def add(self, word, value):\n",
    "        cur = self\n",
    "        for w in word:\n",
    "            cur = cur.childs[w]\n",
    "            cur.pIndexs.append(value)\n",
    "        cur.indexs.append(value)\n",
    "\n",
    "    def get(self, w):\n",
    "        if w not in self.childs:\n",
    "            return None\n",
    "        return self.childs[w]\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\n",
    "        def get_ans(words):\n",
    "            trie = Trie()\n",
    "            ans = []\n",
    "            def isPalindrome(s):\n",
    "                l = 0\n",
    "                r = len(s) - 1\n",
    "                while l < r:\n",
    "                    if s[l] != s[r]:\n",
    "                        return False\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                return True\n",
    "\n",
    "            for j, word in enumerate(words):\n",
    "                n = len(word)\n",
    "                if trie.indexs:\n",
    "                    if isPalindrome(word):\n",
    "                        for i in trie.indexs:\n",
    "                            ans.append([i, j])\n",
    "                cur = trie\n",
    "                for k in range(n-1,-1,-1):\n",
    "                    cur = cur.get(word[k])\n",
    "                    if cur is None:\n",
    "                        break\n",
    "                    #print(word, j, k, cur.indexs)\n",
    "                    for i in cur.indexs:\n",
    "                        if isPalindrome(words[i] + word):\n",
    "                            ans.append([i, j])\n",
    "                if cur:\n",
    "                    q = cur.childs.values()\n",
    "                    for cur in q:                    \n",
    "                        for i in cur.pIndexs:\n",
    "                            if isPalindrome(words[i] + word):\n",
    "                                ans.append([i, j])\n",
    "                trie.add(word, j)\n",
    "            return ans\n",
    "        a = get_ans(words)\n",
    "        b = get_ans(words[::-1])\n",
    "        n = len(words) - 1\n",
    "        # print(b, n)\n",
    "        b = [[n - x, n - y] for x, y in b]\n",
    "        return  a + b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Trie:\r\n",
    "#     def __init__(self) -> None:\r\n",
    "#         self.slots=[None]*26\r\n",
    "#         self.word_id=-1\r\n",
    "#         # self.suffix=[]\r\n",
    "    \r\n",
    "#     def add(self,word:str,id:int):\r\n",
    "#         cur=self\r\n",
    "#         orda=ord('a')\r\n",
    "#         # def is_palindrome(left,right):\r\n",
    "#         #     while left<right:\r\n",
    "#         #         if word[left]!=word[right]:\r\n",
    "#         #             return False\r\n",
    "#         #         left+=1\r\n",
    "#         #         right-=1\r\n",
    "#         #     return True\r\n",
    "#         N=len(word)\r\n",
    "#         for i,ch in enumerate(word):\r\n",
    "#             # if is_palindrome(i,N-1):\r\n",
    "#             #     cur.suffix.append(id)\r\n",
    "#             _ord=ord(ch)-orda\r\n",
    "#             if not cur.slots[_ord]:\r\n",
    "#                 cur.slots[_ord]=Trie()\r\n",
    "#             cur=cur.slots[_ord]\r\n",
    "#         cur.word_id=id\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def palindromePairs(self, words: List[str]) -> List[List[int]]:\r\n",
    "        def build_tree(words:list[str]):\r\n",
    "            root=[None]*27\r\n",
    "            for i,word in enumerate(words):\r\n",
    "                cur=root\r\n",
    "                for ch in word:\r\n",
    "                    idx=ord(ch)-ord('a')\r\n",
    "                    if not cur[idx]:\r\n",
    "                        cur[idx]=[None]*27\r\n",
    "                    cur=cur[idx]\r\n",
    "                cur[26]=i\r\n",
    "            return root\r\n",
    "\r\n",
    "\r\n",
    "        reversed_words=[word[::-1] for word in words]\r\n",
    "        tree=build_tree(words)\r\n",
    "        reversed_tree=build_tree(reversed_words)\r\n",
    "        \r\n",
    "        def is_palindrome(word:str,left,right):\r\n",
    "            while left<right:\r\n",
    "                if word[left]!=word[right]:\r\n",
    "                    return False\r\n",
    "                left+=1\r\n",
    "                right-=1\r\n",
    "            return True\r\n",
    "        \r\n",
    "        def match(wid:int,word:str,tree:list,include_eq:bool):\r\n",
    "            ret=[]\r\n",
    "            if not word:\r\n",
    "                return ret\r\n",
    "            cur=tree\r\n",
    "            L=len(word)\r\n",
    "            for i,ch in enumerate(word):\r\n",
    "                mid=(i+L)//2\r\n",
    "\r\n",
    "                if cur[26]!=None and is_palindrome(word,i,L-1):\r\n",
    "                    ret.append(cur[26])\r\n",
    "                cur=cur[ord(ch)-ord('a')]\r\n",
    "                if not cur:\r\n",
    "                    break\r\n",
    "            else:\r\n",
    "                if cur[26]!=None and include_eq and cur[26]!=wid:\r\n",
    "                    ret.append(cur[26])\r\n",
    "            return ret\r\n",
    "\r\n",
    "\r\n",
    "        \r\n",
    "        ret=[]\r\n",
    "        \r\n",
    "        for i,word in enumerate(words):\r\n",
    "            for j in match(i,word,reversed_tree,True):\r\n",
    "                ret.append([i,j])\r\n",
    "            for j in match(i,word[::-1],tree,False):\r\n",
    "                ret.append([j,i])\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def palindromePairs(self, words):\n",
    "        def is_palindrome(w):\n",
    "            return w == w[::-1]\n",
    "\n",
    "        class Node:\n",
    "            def __init__(self):\n",
    "                self.children = [None] * 26\n",
    "                self.words = []\n",
    "                self.suffixs = []\n",
    "\n",
    "        root = Node()\n",
    "        n = len(words)\n",
    "\n",
    "        for i in range(n):\n",
    "            rev = words[i][::-1]\n",
    "            cur = root\n",
    "            if is_palindrome(rev[0:]):\n",
    "                cur.suffixs.append(i)\n",
    "            for j in range(len(rev)):\n",
    "                ch = rev[j]\n",
    "                if not cur.children[ord(ch) - ord('a')]:\n",
    "                    cur.children[ord(ch) - ord('a')] = Node()\n",
    "                cur = cur.children[ord(ch) - ord('a')]\n",
    "                if is_palindrome(rev[j+1:]):\n",
    "                    cur.suffixs.append(i)\n",
    "            cur.words.append(i)\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for i in range(n):\n",
    "            word = words[i]\n",
    "            cur = root\n",
    "            j = 0\n",
    "            while j < len(word):\n",
    "                if is_palindrome(word[j:]):\n",
    "                    for k in cur.words:\n",
    "                        if k != i:\n",
    "                            ans.append([i, k])\n",
    "\n",
    "                ch = word[j]\n",
    "                if not cur.children[ord(ch) - ord('a')]:\n",
    "                    break\n",
    "                cur = cur.children[ord(ch) - ord('a')]\n",
    "                j += 1\n",
    "\n",
    "            if j == len(word):\n",
    "                for k in cur.suffixs:\n",
    "                    if k != i:\n",
    "                        ans.append([i, k])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
